Simplify OrderPreservingInterner allocation strategy ~97% faster (#2677)#2827
Conversation
4c4b993 to
210a35d
Compare
alamb
left a comment
There was a problem hiding this comment.
I read the code carefully and it makes sense to me. I had one question about test coverage but otherwise 👌
I look forward to seeing how this works
| if &values_buf[slot.value] < data { | ||
| if slots_len == 254 { | ||
| out.push(255); | ||
| self.next |
There was a problem hiding this comment.
Is there coverage of this branch? I think it happens when data is inserted in backwards sorted order, right? Maybe we can add at test to ensure it is covered?
There was a problem hiding this comment.
This branch is hit when the current bucket is "full" and it is trying to insert a value that is greater than the last value in the bucket. This therefore occurs when interning more than 255 values in order, and is therefore hit by test_interner() in particular
let mut values: Vec<_> = (0_u64..2000).collect();
test_intern_values(&values);
I have confirmed this with a debugger
|
Benchmark runs are scheduled for baseline = f4ee8b9 and contender = 65d5576. 65d5576 is a master commit associated with this PR. Results will be available as each benchmark for each run completes. |
Which issue does this PR close?
Closes #2677
Rationale for this change
Not only was the previous allocation strategy quite hard to follow, when interning sorted data it would end up comparing the value against at least
1/4of the already interned values. This was sub-optimal.Taking a step back the original approach of leaving spaces was to mitigate the impact of unsorted data, as the design evolved
OrderPreservingInternernow always sorts the dictionary prior to interning. This dramatically reduces the likelihood of out-of-order inserts, and consequently diminishes the value of this mitigation.A simpler, in-order allocation strategy is both faster and easier to understand
What changes are included in this PR?
Changes the allocation strategy for OrderPreservingInterner to be simpler to understand and faster.
Are there any user-facing changes?
No