Just a bit of experimentation – and lo and behold, it is the random number generation which is killing performance.
Take it out and the freelist is scaling just like the btree.
So – more investigation required, have to see what’s up with the RNG, if I messed it up or it’s just slow.
I actually read something on this matter quite a while ago – about you can’t use modulus *even in single threads* because it’s so slow it kills you. You have to use shift-left/shift-right and powers of 2 only.
I think I’ve run into the same problem.