In D48007#1105192, @markj wrote:

One other performance-related detail I'm wondering about is, we check the iterator limit twice when stepping: once before looking up a leaf, and once after finding one. I believe the latter check is sufficient for correctness. If so, are we making the right tradeoff in checking twice instead of once?

In D48007#1105192, @markj wrote:

In D48007#1103103, @dougm wrote:

In D48007#1102734, @markj wrote:

Are there still some concerns about the overhead of switching to iterators in some of the already-committed changes? I've lost track a bit, I'm sorry.

@alc has concerns. He's reported performance worsened a bit by some of the page management changes already made, and worsened a bit by some other changes that have been under review for a while.

Do we have a benchmark to experiment with, either a workload to test the kernel or a standalone userspace program embedding subr_pctrie.o? I wrote a patch which tries to add a fast path to pctrie_iter_step/next, wherein pctrie.h inlines iteration when the top-most node in the iterator contains a run of successive leaf values, and falls back to pctrie_iter_lookup_ge() to look up new nodes or handle holes. So far I've only tested it to check correctness, but I wonder if it would help performance in the case where a VM object is densely populated.

Undo the parts of the last change about moving the iterator initialization.

In vm_map.c, have page index jump ahead with a superpage jump-ahead. Initialize the cursor before acquiring a read lock.

Fix unused variable problem.

Rebase. Resolve a conflict.

Abandon VM_ALLOC_NOCREAT_LT.

Use VM_RADIX_FORALL in kcov_free.

Use VM_RADIX_FORALL_FROM one more place.

In D48007#1102734, @markj wrote:

Doug, how would you like to proceed with the patch? Since quite a few pieces of it are independent, I imagine they can be reviewed and peeled off one by one, especially in areas that aren't performance-critical.

Define and use VM_RADIX_FOREACH macros. Initialize a couple of iterators before acquiring read locks.

This is a challenging patch to review, and every time I start to review it, I want to rewrite it to make it clearer. I'll hold off one more time. But I really don't think that enums or switches with fallthroughs really help much.

A code reformat to (slightly) reduce the diff size.

The timing results for 8-10 buildworlds, with and without this patch. Without:

Drop the vm_page_iter_free() parts committed elsewhere.

Add a panic when a page duplication is found. Match param names between definition and declaration.

Comments in vm_reserv.c need to be updated to reflect this change.

Define inline pctrie_setpop() to flip popmap bits from 0 to 1 and assert that they have become set. Use it in 3 places.

Remove changes to vm_page_iter_remove.

Pass the removed page to vm_page_iter_remove, and functions that use it. Update comments. Reorder declarations.

Apply suggestions from feedback on D46724 to improve performance.

Drop the fix that @kib has committed separately.

Drop length argument to cdev_mgtdev_pager_free_pages().

Fix typo in tegra_bo.c.

Use vm_radix_iter_found in swap_pager.c. Tweak the pctrie.h implement to avoid a pointless null check.

Avoid the object != NULL check in vm_page_iter_free.

alc update 11/16.

Drop the bool argument from vm_page_free_toq. Turn vm_page_free_toq into a wrapper for the real implementation function, to which it passes 'true' as the bool argument.

Update some comments.

Remove changes to subr_pctrie.c. Pass the iterator to vm_page_rename() to allow the page to be removed with the iterator and the appropriate page number.

Rename vm_page_object_remove.

Rearrange into vm_page_iter_remove and vm_page_iter_free iter-based substitutes for the iter-less equivalents.

Performance test:
Ran 12 buildworlds, without and with this change, on an amd64 machine to verify it did not harm performance there.
Without:

Rebase. Undo some function reordering that makes this reviewer easier, even if it preserves some odd ordering.

Rebase.

Refresh.

If you're inserting batch [a,b,...,y.z], and if you began by inserting a and z with normal iter-insert, then your BATCH_SPLIT case would never happen and some of the complexity of batch_insert could be reduced. True or false?

In D47036, I put it after vm_radix_iter_step, mostly because PCTRIE_ITER_LOOKUP_LE comes shortly after PCTRIE_ITER_STEP_GE in pctrie.h. 'step' and 'jump' are built on top of lookup_ge, so I kept them grouped with lookup_ge.