Change Details

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 {F5541195} Test 2 {F5541230} Reran tests with ic-misses and retired instructions stats from pmcstat. The ic-misses stats are terrible. 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 609922345 52663323 73972741885 17.661147 596699780 52969931 73972848442 17.615362 604299829 53396749 73973114629 17.654081 604772511 53927893 73977610293 17.663508 598277048 52823219 73972950105 17.669119 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 568285673 52765402 72022820060 16.796551 575880774 52625590 72022632357 16.823366 571467417 53197894 72022526987 16.776770 573588506 53706365 72028629931 16.788188 573141276 52630602 72022287531 16.763158

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 {F5541195} Test 2 {F5541230} 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 609922345 52663323 73972741885 17.661147 596699780 52969931 73972848442 17.615362 604299829 53396749 73973114629 17.654081 604772511 53927893 73977610293 17.663508 598277048 52823219 73972950105 17.669119 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 568285673 52765402 72022820060 16.796551 575880774 52625590 72022632357 16.823366 571467417 53197894 72022526987 16.776770 573588506 53706365 72028629931 16.788188 573141276 52630602 72022287531 16.763158

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 {F5541195} Test 2 {F5541230} Reran tests with ic-misses and retired instructions stats from pmcstat. The ic-misses stats are terrible. 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 609922345 52663323 73972741885 17.661147 596699780 52969931 73972848442 17.615362 604299829 53396749 73973114629 17.654081 604772511 53927893 73977610293 17.663508 598277048 52823219 73972950105 17.669119 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 568285673 52765402 72022820060 16.796551 575880774 52625590 72022632357 16.823366 571467417 53197894 72022526987 16.776770 573588506 53706365 72028629931 16.788188 573141276 52630602 72022287531 16.763158