specialize offsets map

[danhhz]

The offsets map is currently implemented with FastIntMap since it was convenient, but FastIntMap has to either be tuned in one general way or else multiple versions code generated to get the nice compiler specializations for all the masks. We could make the happy zero-allocation case more likely if we specialize it at code generation time using our knowledge of the message fields.

For densely packed fields an array is sufficient. It'd be easiest to start with a []uint32 but the values are offsets into a message and so we likely don't need the full range of 4294967296, so that would use more space than necessary. Maybe a followup to make it smaller? We'd have a similar problem to FastIntMap then where we'd have to have all the various sizes we want to use in the zeropb package (or maybe codegen the crazy ones into the generated proto code, eek). We also have to decide how to handle offsets that are larger than whatever range we pick. If we want any valid input to work, we need to fall back to allocating a map and we've basically re-derived FastIntMap (this is exactly why I used it in the first place).

My initial thought is starting with []uint32 and eating the struct size. That's definitely the simplest. It's also not as bad as it sounds. Most of the fields that would be generated other protobuf libraries are 4-8 bytes per field, which means best case is the same size struct and worst case is 2x. Sigh, maybe uint16 really is the way to go, seems like 65536 bytes should be enough. Instead of the map fallback, decode could error if given a buffer longer than max offset, which seems like a reasonable limitation.

If we do specialize densely packed fields, we need a heuristic and also a second impl for non-densely packed fields. My initial idea for the heuristic is if there are no more holes than fields. That is, if max field id <= 2 * num fields. The second impl could initially always be a map (unfortunate but predictable performance). We could add a proto option to let the user override the heuristic if they're okay with the tradeoff.

Both offset impls would be structs that happen to expose the same set of methods. Then the codegen would simply put one or the other in the generated message struct and the rest of the codegen would be the same. No interfaces so no allocations.

There's probably things we could eventually do to improve the second impl if we cared (though I initially do not). It could be an array (of a size computed by some heuristic over the field types) and a slice view of that array (or I guess it'd have to be two of these?). Then we keep all the fields sorted and do everything via binary search, appending to add new parsed fields. That would be allocation free until we got too many fields, which isn't bad. It also doesn't have the unpredictability of FastIntMap's flip from small to large.