Description
In #95809 we prototyped a sorted keys iterator for LongKeyedBucketOrds, using a Java TreeSet. Using a tree set here has many benefits, notably logarithmic insertion time, and a naturally sorted iterator. However, the use of the Java Collections implementation means the memory used for this isn't tracked in our circuit breaker. To solve this, I propose building a data structure with the beneficial properties of a tree set, backed by a BigArray.
Description
In #95809 we prototyped a sorted keys iterator for
LongKeyedBucketOrds, using a JavaTreeSet. Using a tree set here has many benefits, notably logarithmic insertion time, and a naturally sorted iterator. However, the use of the Java Collections implementation means the memory used for this isn't tracked in our circuit breaker. To solve this, I propose building a data structure with the beneficial properties of a tree set, backed by aBigArray.