Change the vm_map tree so that it is threaded; where a NULL pointer appears as a left child now, point to the previous item, and where a NULL pointer appears as a right child, point to the next item. Where there is no previous or next item, point to the map header.
Remove the prev pointer, and use a simple walk - of expected length 2 - to find it using left and right pointers. Take more opportunities to keep trailing pointers when iterating forward, to avoid unnecessary calculation.
Remove the next pointer. Where it is used to keep a stack of idle map entries, use the right field instead. Where it is used to find the next entry in the ordered set, use a function to calculate that entry.
The change reduces the size of vm_map_entry, obviously. On a pair of tests that do nothing but create and free map entries, it reduces running time and data cache miss counts slightly.
{F5541195}
Modified
time, dc-misses, 5 tests
18.469429 612149521
18.513463 626840441
18.493864 606433178
18.436925 612354290
18.500854 610673693
Original
time, dc-misses, 5 tests
18.919835 664324381
19.31932 681685132
18.940139 665389818
18.917524 675577608
18.922143 652591840
{F5541230}
Modified
time, dc-misses, 5 tests
17.633731 580057420
17.709786 599025250
17.681210 579837458
17.617679 567257058
17.720645 566887599
Original
time, dc-misses, 5 tests
18.44355 629452843
18.184409 626960073
18.199191 633834727
17.992720 625547426
17.986247 619292654
On a test that mostly just walks the list of entries, performance is slightly reduced, since there is no precomputed 'next' pointer to follow.
{F5541261}
Modified, times, 10 samples
0.31
0.32
0.31
0.30
0.31
0.30
0.31
0.31
0.30
0.31
Original times, 10 samples
0.30
0.28
0.27
0.27
0.29
0.27
0.29
0.27
0.26
0.28