Right now, the blist has to perform a lot of checking after each comparison operation to make sure the comparison function did not permute the list. We could save a lot of time by making an O(1) copy first.
I'm not sure if that would pay off for small lists (where the root is also a leaf), but it might.
For long lists, it should be a clear win. We should probably be careful to avoid starting the cache in the root which would use O(n) memory.
Right now, the blist has to perform a lot of checking after each comparison operation to make sure the comparison function did not permute the list. We could save a lot of time by making an O(1) copy first.
I'm not sure if that would pay off for small lists (where the root is also a leaf), but it might.
For long lists, it should be a clear win. We should probably be careful to avoid starting the cache in the root which would use O(n) memory.