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 deferred list of 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 data cache miss counts and slightly increases run time.
Test 1
Test 2
Reran tests with ic-misses and retired instructions stats from pmcstat.
Test 1, before
s/00/dc-misses s/00/ic-misses s/00/instructions time 640126288 189963218 68389420159 17.183823 635966376 188903061 68383732671 17.136943 645576968 187442527 68383619075 17.244985 641578297 190145438 68383361081 17.186198 643313499 193056507 68383326531 17.249235
Test 1, after
s/00/dc-misses s/00/ic-misses s/00/instructions time 625740686 42856465 73497547534 17.382173 615782289 41645451 73497370425 17.355385 621791871 43549885 73497607344 17.412323 621381530 46539739 73497547503 17.430227 614402301 42532386 73497248665 17.307636
Test 2, before
s/00/dc-misses s/00/ic-misses s/00/instructions time 609155004 183879088 66508137909 16.320631 615834730 184101900 66501366693 16.336226 618390676 184364082 66501780532 16.400097 609124953 184059016 66501644482 16.361776 609934927 184430198 66501727209 16.349004
Test 2, after
s/00/dc-misses s/00/ic-misses s/00/instructions time 581142919 43054092 71751406088 16.507261 584860285 47687381 71744859944 16.575260 578066986 42316363 71744755831 16.503378 579061559 41838134 71744611514 16.543057 593114238 40905403 71745027601 16.517714