pctrie: Introduce batch pctrie insertion routines

[bnovkov]

Summary

This change introduces routines optimized for inserting multiple
items into the pctrie. The main goal is to provide a more performant
and cache-friendly way of inserting multiple items into the pctrie.

pctrie_batch_insert uses a special, iterator-based lookup function
to find or construct a 0-level pctrie node. The target node is then
filled up with as many items as possible and the process is repeated
until all items are inserted. The routine will stop inserting if
it was not able to allocate a pctrie node.

Test Plan

Aside from the performance evaluation in D47051, I've also evaluated this change by comparing the average number of cycles it takes to insert N items into the pctrie.
The cycle count for each batch size was averaged across 100 runs.

no. items	forloop + iter_insert cycle count	pctrie_batch_insert cycle count	percentage of cycles saved
1	103	106	-2.83
2	290	192	51.04
4	259	190	36.32
8	379	194	95.36
16	622	205	203.42
32	1258	422	198.10
64	2420	678	256.93
128	4655	1216	282.81
256	9238	2224	315.38
512	18427	4547	305.26
1024	37113	9049	310.13
2048	74888	18477	305.30
4096	150373	37571	300.24
8192	301584	75992	296.86
16384	608159	154314	294.10

[dougm]

This is more complex than initializing and iterator and using it to insert consecutive elements. How have you measured its performance and cache-friendliness in comparison to that simpler implementation?

sys/kern/subr_pctrie.c

717

What happens if there's already a value stored at node? What should happen?

718

It seems you can set *out to parent here and drop all the other assignments to *out. Can't the caller invoke _get_parent to get this value?

721

Is a special case necessary here? This function doesn't modify the tree, except in this case. Isn't this another special case for ALLOC_INSERT?

783

How do you know that there isn't already something stored here? What should you do in that case?

817

I think that your array of elements are constrained to have consecutive indices, but I don't see comments about that. And since you're reading index values from the data, it seems that if those indices aren't consecutive, this is going to wreck the tree. So perhaps this function should take an index argument for the first array element and do the assignment of consecutive index values to the array elements so that the tree cannot be wrecked.

[bnovkov]

In D47044#1072595, @dougm wrote:

This is more complex than initializing and iterator and using it to insert consecutive elements. How have you measured its performance and cache-friendliness in comparison to that simpler implementation?

The whole patch series was evaluated, but I haven't measured the performance gain for this change only.
I've updated the test plan with the results of a simple microbenchmark comparing iter_insert and pctrie_batch_insert.

Also, thank you for pointing out the consecutive indices constraint, this indeed is the case and I completely forgot to note that in the comments. I'll address this along with your other comments later today.

[bnovkov]

Address @dougm 's comments:

• Removed a redundant pctrie_batch_lookup_result enum
• pctrie_batch_insert now takes a starting key instead of relying on items having contiguous keys pre-filled

[bnovkov]

sys/kern/subr_pctrie.c

717

The test consumer of this interface performs an explicit lookup prior to insertion so this slipped by me.

My first reaction would be to check before insertions and panic if there's already a value stored.
This would slow things down a bit, but it's consistent with how we've been doing things so far.
We could also perform an explicit lookup before inserting anything and trim the insertion range accordingly

I'm not sure which approach would make more sense though.
The same goes for the other two similar comments out below.

721

Right, the case is redundant, I've removed it and handled the single-item insertion case in pctrie_batch_insert.

817

Thanks for pointing this out, this indeed is the case.
I've modified the function according to your suggestion, it'll now take a starting index and populate the elements instead of relying on them being properly prefilled.

[dougm]

sys/kern/subr_pctrie.c

719

If parent == NULL, and you've already assigned *out = parent, you don't need to assign *out = NULL.

724

Don't need the 'else'. Don't need so many braces.

751

You don't need to assert node != NULL. The system already checks that assertion for you.

758

"- n" doesn't contribute much here.

It seems that nitems and to_insert don't overlap. Why not replace to_insert with nitems?

759

It seems that you are error-handling by assertion. If I try to enter elements 100-199 in the pctrie and element 143 is there already, this assertion will fail. But if I've built the kernel GENERIC-NODEBUG, this assertion is disabled and I will lose element 143. So, is the user required to check that the least element >= 100 is > 199 to make sure they're all missing before entering 100-199 all at once?

I've wondered if this thing you're doing is for mass-insertion at an arbitrary point in the life of the pctrie, or is instead for initialization of the pctrie only. If this were an initializer only, these pesky questions I'm asking would just disappear.

779

I wonder if this needs to be locked.

I haven't figured out all your code yet, but I'm wondering if you're modifying the original pctrie a few pieces at a time, and using PCTRIE_LOCKED ever 16 writes or so, when you could do something else. Suppose you designed this to build an entire little pctrie of values 100-199, or whatever, and then attach it all at once to the big pctrie. The building of the little pctrie could be completely unsynchronized. Only when you inserted the little pctrie into the big pctrie would the last store have to be synchronized. So I expect that would improve performance.

If this is just an initializer, most of above still applies; you don't need PCTRIE_LOCKED until the pctrie is ready.

[bnovkov]

Address @dougm 's comments:

• Removed redundant assignment and pruned code
• Moved checks for existing elements outside of assertions

[bnovkov]

sys/kern/subr_pctrie.c

758

Ah, right, that was a bit silly - thanks for catching this!

759

So, is the user required to check that the least element >= 100 is > 199 to make sure they're all missing before entering 100-199 all at once?

I think its best if we performed the checks when inserting, the popmap is now always checked during batched insertion.

I've wondered if this thing you're doing is for mass-insertion at an arbitrary point in the life of the pctrie, or is instead for initialization of the pctrie only. If this were an initializer only, these pesky questions I'm asking would just disappear.

The former is true, this is meant to be used at any point of the pctrie's lifecycle.

779

I wonder if this needs to be locked.

I haven't figured out all your code yet, but I'm wondering if you're modifying the original pctrie a few pieces at a time, and using PCTRIE_LOCKED ever 16 writes or so, when you could do something else. Suppose you designed this to build an entire little pctrie of values 100-199, or whatever, and then attach it all at once to the big pctrie. The building of the little pctrie could be completely unsynchronized. Only when you inserted the little pctrie into the big pctrie would the last store have to be synchronized. So I expect that would improve performance.

I had considered this approach initially but ultimately settled for another approach since this idea seemed even more complex and trickier to get right. Would it make sense to do a similar thing with the current patch - i.e. synchronize only at the very last write?

[dougm]

sys/kern/subr_pctrie.c

540

A function so small, used only once, is best avoided.

709

nitems is not used in this function.

Is an enum type and this function really necessary, since it's only called once? Can't this just be logic in pctrie_batch_insert?

716

Reorder the tests so that you don't need so many nesting levels.

758

How about a for loop?

763

Instead of modifying slot with every iteration, how about slot + n here?

798

*val always has the same value assigned to it. Might as well do it one place instead of 3.

799

Some expressions below use 'index' and some use 'start + total'. Pick one.

808

I don't see the point of this assignment.

[bnovkov]

Address @dougm 's comments.

[bnovkov]

sys/kern/subr_pctrie.c

709

It could, but I deliberately split the lookup part out to keep pctrie_batch_insert smaller and easier to read.

[dougm]

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?

[dougm]

sys/kern/subr_pctrie.c

717

I'm going to keep picking at this until this function and this enum goes away, but for now, can you write it to have only 2 if statements and 3 return statements?

793

	val = pctrie_iter_lookup_ge(it, start);
	if (val != NULL && *val <= start + nitems - 1)
		panic("%s: key '%lu' already present", __func__, *val);

Now you don't need any other panic tests in the code.

806

I observe that the rest of the code in this file does not wrap single lines after if, like this one, in braces. Don't adopt a unique style for this function.

843

Correct me if I'm wrong. This happens only when inserting the first item. If, before the loop begins, you check to see if (start + 1) % PCTRIE_COUNT == 0 and, if so, insert the first item with iter_insert and increase total to 1, then this case doesn't have to be checked here in the loop.

905

	} while (total < nitems - 1);

Now, there are three places where you can stop checking for nitems - total == 1 in the code, and instead, here you can just test for total != nitems and do an iter_insert in that case.

[bnovkov]

Address @dougm 's comments:

• Removed separate lookup function and enum type
• Explicit range lookup before insertion
• Moved pctrie_iter_insert to subr_pctrie.c so it can be used for single-element insertions

[bnovkov]

In D47044#1079505, @dougm wrote:

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?

I think you're right, values less than a and greater than z could be occupying their slots in an internal node, and there should be no other nodes between those if the pctrie_iter_lookup_ge check goes through.
However, removing the 'SPLIT' case and performing an out-of-order insertion of a and z leaves us with a tricky issue - what if any of the subsequent insertions fail?
That is, how would we signal the fact that we managed to insert only, e.g., a, b, and z?

sys/kern/subr_pctrie.c

717

After addressing a couple of your other remarks the lookup function slimmed down to a couple of lines, so I moved everything to pctrie_batch_insert.
The enum is still there since rewriting switch-case code would be cumbersome, but it's now part of the batch insert routine.

843

That is indeed the case, thanks for catching this!

[dougm]

sys/sys/pctrie.h

241

When I merged vm_radix.c with subr_pctrie.c so that there would be only one implementation of pctries, it was accepted, in part, because I made sure to avoid passing pointers to memory allocators to any functions. Otherwise, we'd still have a separate vm_radix implementation. So casually changing that by turning this function into one that passes a function pointer to a memory allocator is not acceptable.

[bnovkov]

sys/sys/pctrie.h

241

Right, I'll revert this part but I'll still need to access this from subr_pctrie.c somehow.
Would having a separate static version of pctrie_iter_insert in subr_pctrie.c be okay? Bouncing back and forth between pctrie.h and subr_pctrie.c to allocate nodes is something I want to avoid, if possible.

[dougm]

sys/sys/pctrie.h

241

Bouncing is bad.

The number of pctrie_nodes you have to allocate is bounded by something like nitems/(PCTRIE_COUNT-1) + 1. If you figure the quantity precisely, you can pre-allocate all the nodes at the top level as pass an array of pointers to them to the batch_insert function.

[bnovkov]

Address @dougm 's comments:

• reverted pctrie_iter_insert change
• removed allocfn from pctrie_batch_insert by passing an array of preallocated pctrie nodes

[bnovkov]

sys/sys/pctrie.h

241

I've converted the batch_insert function to follow this approach, although this might slow down cases where nitems == 1 since node allocation is pretty much guaranteed now.
We can avoid that by doing a regular pctrie_iter_insert, but I'm not sure whether this should be handled in _PCTRIE_INSERT_BATCH or in the pctrie consumers (e.g., vm_radix).

[dougm]

sys/sys/pctrie.h

193

I don't think this is enough nodes. If the pctrie is empty, start is 0 and nitems is 768, then you allocate 50 nodes, but you need 48 at the bottom level and 3 at the level above that, and one at the root, so you have too few. I suggested previously nitems / (PCTRIE_COUNT - 1) + 1 as a starting point. Dividing by PCTRIE_COUNT-1 was not a typo; it's how you account for nodes at all levels in an empty trie. 768/15 == 52 works in this case. I was hoping that you would calculate the exact number needed, which also depends on whether the first and/or last leaf will be added to an already allocated leaf. I didn't expect an approach of allocating too many and then freeing the ones you didn't turn out to need. You should write a function that uses the iterator, start and nitems to calculate exactly how many allocations you need. I could write one if you need me to.