Improvements to BooleanBufferBuilder / BooleanBuilder

[jhorstmann]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

BooleanBufferBuilder / BooleanBuilder seem to currently serve two quite distinct usecases, which makes it more difficult to get the best possible performance for both of them.

• Building a new buffer by starting from an empty state and incrementally appending new bits (append_value, append_slice, append_packed_range and similar methods).
• Starting from a buffer that is initialized to ones/zeroes or a copy of an existing buffer, modifying certain bits in it (set_bit, get_bit).

(This is based my analysis of the arrow-rs code only, the assumption should also be verified against some bigger users like datafusion.)

The first usecase can be optimized by collecting bits to append in a u64 and only appending the corresponding bytes to memory every 64 appended values. Any capacity checks are thus amortized over those 64 values. On the other hand, methods to get and set arbitrary bit positions would be a bit less efficient to implement in this scheme.

The second usecase should not need any logic to resize the buffer and so could be much simpler.

Describe the solution you'd like

I think it would make sense to also separate these usecases in code, by introducing separate BooleanBufferBuilder and MutableBooleanBuffer implementations.

Since this would involve breaking the existing api, it would probably have to be done in multiple steps. First introducing a separate MutableBooleanBuffer and deprecating the set_bit / get_bit functionality, and only afterwards refactoring the BooleanBuilder.

Describe alternatives you've considered

Additional context

Noticed while looking into #8543

[alamb]

(This is based my analysis of the arrow-rs code only, the assumption should also be verified against some bigger users like datafusion.)

I agree this captures the usecases succinctly

For the first "incremental" usecase that is often an iterator (of either bool or Option<bool>) in some form or other

[alamb]

Since this would involve breaking the existing api, it would probably have to be done in multiple steps. First introducing a separate MutableBooleanBuffer and deprecating the set_bit / get_bit functionality, and only afterwards refactoring the BooleanBuilder.

We could also potentially leave the existing set/get functionality (deprecated) and optimize BooleanBuilder for the append case, which wouldn't technically be a breaking API (though users might experience a performance regression if they continued to use the old APIs)

cc @tobixdev @tustvold @crepererum for your comments

[tobixdev]

I am a fan of trying to eliminate the current allocation in the extend implementation using some finite-size buffer (e.g., u64) if this has at similar (or better) performance than the Vec allocation.

I am not too familiar with the use of the builder in arrow but I am having troubles of how we the two use cases are mutually exclusive to optimize in a single builder. Couldn't we optimize the BooleanBuilder / BooleanBufferBuilder for the first use case and, if necessary, offer a get_bit_raw and set_bit_raw similar to arrow_buffer::bitutil that allows switching bits on/off efficiently? This could then also circumvent any bounds checks and therefore support the second use case. Could you maybe provide an example?

[alamb]

BooleanBufferBuilder / BooleanBuilder seem to currently serve two quite distinct usecases, which makes it more difficult to get the best possible performance for both of them.

I looked a little more into the APIs

it seems like BooleanBuilder is the one that is for appending new values, and BooleanBufferBuilder is for getting/setting individual bits

The major difference is that BooleanBufferBuilder doesn't handle nulls...

[alamb]

In case anyone else is following along here is the code in question:

arrow-rs/arrow-array/src/builder/boolean_builder.rs

Lines 234 to 244 in ba22a21

	impl Extend<Option<bool>> for BooleanBuilder {
	#[inline]
	fn extend<T: IntoIterator<Item = Option<bool>>>(&mut self, iter: T) {
	let buffered = iter.into_iter().collect::<Vec<_>>();
	let array = unsafe {
	// SAFETY: std::vec::IntoIter implements TrustedLen
	BooleanArray::from_trusted_len_iter(buffered.into_iter())
	};
	self.append_array(&array)
	}
	}

This actually has 2 allocations

I think it would be possible to do something like:

1. take as many elements from the iterator as needed to completely fill the underlying buffers up to a u64 boundary
2. Then take() in 64 element sections, writing into the relevant u64s
3. Appending the u64 to the underlying buffer

[alamb]

Actually, it looks like maybe we could just do use https://docs.rs/arrow/latest/arrow/array/struct.BooleanBufferBuilder.html#method.append_packed_range

to append the u64 🤔

[alamb]

Update here:

• I think we can use this PR from @rluvaton and myself: feat: add apply_unary_op and apply_binary_op bitwise operations #8619 to improve append_packed_range. I made a PR to do so: Change BooleanBuffer::append_packed_range to use apply_bitwise_binary_op #8812
• I also tried adding a special case for applying bitwise operations using u64 math, and it looks quite promising: WIP: special case bitwise ops when buffers are u64 aligned #8807

[alamb]

I also have some other ideas about APIs might look like to support the create new vs modification APIs here (rather than adding a new mutable buffer)

• Consolidate bitwise operation implementations #8806
• [Arrow] Add bitwise operations BooleanArray that potentially reuse the underlying allocaton #8809