The text below is from an old version of the timings from the hypellfrob page.

These are timings for random hyperelliptic curves over GF(p), performed on sage.math, a 1.8GHz AMD Opteron (thanks to William Stein), using hypellfrob version 2.0 and zn_poly version 0.4.

For genus 2, we computed the charpoly mod p, which determines essentially all the information. For genus 3, we also compute the charpoly mod p, which leaves half a digit to be recovered by e.g. baby-step/giant-step. For genus 4, we computed the charpoly mod p^2, which determines essentially everything.

pgenus 2genus 3genus 4
2^16 + 1 0.008s 0.020s 0.16s
2^20 + 7 0.044s 0.092s 0.92s
2^24 + 43 0.324s 0.648s 20.3s
2^28 + 3 2.95s 5.9s 111s
2^32 + 15 21.6s 43.3s 1313s