So, I redid the @michaelwoerister's experiment and got very similar results.
The setup was slightly different - I didn't collect span statistics from AST before or after expansion, I recorded every span created with Span::new instead (this requires https://github.com/rust-lang/rust/pull/43968).
I also reimplemented the program tabu-searching for optimal encodings independently, so bug compatibility with @michaelwoerister's version is unlikely.
First of all, what percentage of spans can we represent with a certain number of bits? Here's some chart.
This chart is too optimistic, because it assumes that the number of possible encodings can be used is unlimited.
We see however, that the center of the step is around 24 bits, so it's reasonable to look for encodings for 32 and 40 bit compressed spans (I looked for 24 bit as well, for comparison).
The search space looks like this: (base, offset, ctxt, is_negative_offset).
base is span.lo (position in the codemap), offset is abs(span.hi - span.lo), ctxt is index into interner for various hygiene- and macro-related data, is_negative_offset is is_negative(span.hi - span.lo) (yes, there are spans with span.lo > span.hi! I'm going to eliminate them soon though).
I looked for optimal encodings with 1-, 2- and 3-bit tag.
Simple tabu search likes to stuck in local maximums, so the results are slightly different when we start searching from (large, 0, 0, 0) and (equal, equal, equal, 1), I'm listing all of them below.
# 24 bits
[(20, 3, 0, 0)], representable: 28.0945636582%
[(21, 1, 0, 0), (20, 2, 0, 0), (18, 4, 0, 0)], representable: 29.5463886348%
[(20, 2, 0, 0), (18, 4, 0, 0), (15, 7, 0, 0)], representable: 28.2045555975%
[(21, 0, 0, 0), (21, 0, 0, 0), (21, 0, 0, 0), (21, 0, 0, 0), (20, 1, 0, 0), (18, 3, 0, 0), (14, 1, 6, 0)], representable: 20.3942652242%
[(20, 1, 0, 0), (19, 2, 0, 0), (17, 4, 0, 0), (14, 7, 0, 0), (6, 7, 7, 1), (6, 7, 7, 1), (0, 6, 14, 1)], representable: 22.8205040856%
# 32 bits
[(24, 7, 0, 0)], @michaelwoerister's result
[(24, 7, 0, 0)], representable: 80.010087496%
[(24, 6, 0, 0), (21, 9, 0, 0), (17, 4, 9, 0)], @michaelwoerister's result
[(24, 6, 0, 0), (22, 8, 0, 0), (18, 1, 11, 0)], representable: 82.6795242211%
[(23, 7, 0, 0), (18, 4, 8, 0), (18, 1, 11, 0)], representable: 79.8442320036%
[(29, 0, 0, 0), (29, 0, 0, 0), (29, 0, 0, 0), (29, 0, 0, 0), (24, 5, 0, 0), (22, 7, 0, 0), (17, 1, 11, 0)], representable: 79.9041099684%
[(24, 5, 0, 0), (22, 7, 0, 0), (20, 9, 0, 0), (18, 3, 8, 0), (17, 1, 11, 0), (16, 5, 8, 0), (5, 24, 0, 0)], representable: 81.6788671615%
# 40 bits
[(24, 15, 0, 0)], representable: 84.5305650395%
[(38, 0, 0, 0), (24, 14, 0, 0), (21, 4, 13, 0)], representable: 92.5187443371%
[(24, 14, 0, 0), (21, 4, 13, 0), (20, 6, 12, 0)], representable: 93.4870459248%
[(37, 0, 0, 0), (37, 0, 0, 0), (37, 0, 0, 0), (37, 0, 0, 0), (37, 0, 0, 0), (24, 13, 0, 0), (20, 5, 12, 0)], representable: 91.8228933713%
[(24, 13, 0, 0), (21, 3, 13, 0), (20, 5, 12, 0), (19, 7, 11, 0), (18, 11, 8, 0), (16, 10, 11, 0), (15, 8, 14, 0)], representable: 93.5323612314%
As expected, 24 bits is too small to keep anything.
32 bits and 40 bits give much better percents than 24 bits, but 40 bits is not significantly better than 32 bits.
3 bits of tag seems to be too much unless we use really large number of bits for the whole span.
Going from percents to absolute numbers, even if we assume that interned spans spend 3 times more memory due to interning overhead, 32 bit still seem to win over 40 bit:
cost32 = 32, cost40 = 40, percent32 = 0.8268, percent40 = 0.9349
cost32 * percent32 + 3 * cost32 * (1 - percent32) < cost40 * percent40 + 3 * cost40 * (1 - percent40)
43.0848 < 45.2080
If we add extra padding that will be more likely generated by 40 bit spans, the difference will become even larger.
As a result, I'm going to implement 32-bit compressed spans with 2-bit tag and encodings (24, 6, 0, 0), (22, 8, 0, 0), (18, 1, 11, 0).
EDIT: And I'm also going to use [u8; 4] instead of u32 to avoid bumping alignment requirements for structs containing spans.