You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "klion26 (via GitHub)" <gi...@apache.org> on 2025/07/16 06:10:15 UTC
[PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
klion26 opened a new pull request, #7935:
URL: https://github.com/apache/arrow-rs/pull/7935
# Which issue does this PR close?
- Closes #7899 .
This pr wants to avoid the extra allocation for the object builder and the later buffer copy.
# Rationale for this change
Avoid extra allocation in the object builder like the issue descripted.
# What changes are included in this PR?
- add `object_start_offset` in `ObjectBuilder`, which describes the start offset in the parent buffer for the current object
- Add `has_been_finished` in `ObjectBuilder`, which describes whether the current object has been finished; it will be used in the `Drop` function.
- Modify the logic of `new`, `finish`, `parent_state`, and `drop` function according to the change.
# Are these changes tested?
The logic has been covered by the exist logic.
# Are there any user-facing changes?
No
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2221261706
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
~~There will be no waste here, this is where I made a mistake before~~
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3094634597
@alamb thank you very much for the review and help, happy to see these improvements.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217930441
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
+ let id_size = int_size(max_id);
- let id_size = int_size(max_id as usize);
+ let parent_buffer = self.parent_state.buffer();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
Review Comment:
Oh, I forgot that parent status has exclusively access to the parent buffer.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217933884
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
+ let id_size = int_size(max_id);
- let id_size = int_size(max_id as usize);
+ let parent_buffer = self.parent_state.buffer();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
let offset_size = int_size(data_size);
- // Get parent's buffer
- let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
- // Write header
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(
+ starting_offset..starting_offset,
+ std::iter::repeat_n(0u8, header_size),
+ );
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
Review Comment:
This is basically `append_header` did before, right? Maybe we can also extract to a function instead of inline here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2219153630
##########
parquet-variant/src/builder.rs:
##########
@@ -1317,7 +1414,15 @@ impl<'a> ObjectBuilder<'a> {
/// This is to ensure that the object is always finalized before its parent builder
/// is finalized.
impl Drop for ObjectBuilder<'_> {
- fn drop(&mut self) {}
+ fn drop(&mut self) {
+ // truncate the buffer if the `finish` method has not been called.
+ if !self.has_been_finished {
+ self.parent_state
+ .buffer()
+ .inner_mut()
+ .truncate(self.object_start_offset);
+ }
Review Comment:
Yes, existing tests expect the fields to persist because the original code was _unable_ to roll back the changes. With this PR, we should be able to roll back the changes cleanly, and update the unit tests accordingly.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3104275977
🤖 `./gh_compare_arrow.sh` [Benchmark Script](https://github.com/alamb/datafusion-benchmarking/blob/main/gh_compare_arrow.sh) Running
Linux aal-dev 6.11.0-1016-gcp #16~24.04.1-Ubuntu SMP Wed May 28 02:40:52 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Comparing 7899-avoid-extra-allocation-in-object-builder (19bb544be4b049c4fb0ad7ad0d35149655959f4e) to 291e6e575c727a98ee52b617da0c8de64a821e09 [diff](https://github.com/apache/arrow-rs/compare/291e6e575c727a98ee52b617da0c8de64a821e09..19bb544be4b049c4fb0ad7ad0d35149655959f4e)
BENCH_NAME=variant_kernels
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental --bench variant_kernels
BENCH_FILTER=
BENCH_BRANCH_NAME=7899-avoid-extra-allocation-in-object-builder
Results will be posted here when complete
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3105699838
@alamb @scovich @viirya Thank you for the review; I learned a lot from this PR. I've created issues #7977 and #7978 to track the follow-up
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2209376279
##########
parquet-variant/src/builder.rs:
##########
@@ -955,13 +967,48 @@ impl<'a> ObjectBuilder<'a> {
// Returns validate_unique_fields because we can no longer reference self once this method returns.
fn parent_state<'b>(&'b mut self, key: &'b str) -> (ParentState<'b>, bool) {
- let state = ParentState::Object {
- buffer: &mut self.buffer,
- metadata_builder: self.parent_state.metadata_builder(),
- fields: &mut self.fields,
- field_name: key,
- };
- (state, self.validate_unique_fields)
+ let validate_unique_fields = self.validate_unique_fields;
+
+ match &mut self.parent_state {
Review Comment:
Did find a better solution for this, I can change this if there is a better solution.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217431963
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
Review Comment:
FYI, I think we can improve the performance of appending packed `u32` values to a `Vec<u8>`. The following code:
```rust
pub fn append_bytes_brute2(dest: &mut Vec<u8>, src: u32, nbytes: NumBytes) {
let n = dest.len() + nbytes as usize;
dest.extend(src.to_le_bytes());
dest.truncate(n);
}
```
... unconditionally adds all four bytes and then truncates the vector to the desired length. This works because (a) it's a single machine instruction to copy the four LE bytes of a `u32` to a memory location; and (b) `truncate` is dirt cheap (conditional move that doesn't break processor pipelines the way a branch would).
Result: Code that should perform the same regardless of the number of bytes we encode the `u32` as, with only a single branch to check for vector capacity.
<details>
The above [compiles](https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=c4e3f95d39ad58148435d55ff7095a3a) to the following assembly code:
```asm
playground::append_packed_u32:
;; set up stack frame (not relevant in practice due to inlining)
...
movq (%rdi), %rcx ; dest capacity
movq 16(%rdi), %rbx ; dest len
subq %rbx, %rcx ; calculate available capacity
movq %rbx, %rax
cmpq $3, %rcx ; if insufficient capacity...
jbe .LBB2_1 ; ... then `reserve` more
.LBB2_2:
addq %rdx, %rbx ; add nbytes to len (truncate arg)
movq 8(%rdi), %rcx ; dest data pointer
movl %esi, (%rcx,%rax) ; append all four bytes of src to the vector
addq $4, %rax ; increase len by 4 (u32 size)
cmpq %rax, %rbx ; if new len is bigger than truncate arg...
cmovbq %rbx, %rax ; ... then truncate len
movq %rax, 16(%rdi) ; write back the updated dest len
;; tear down stack frame
...
retq
.LBB2_1:
;; call prologue
...
callq alloc::raw_vec::RawVecInner<A>::reserve::do_reserve_and_handle
;; call epilogue
...
jmp .LBB2_2
```
The one bummer is, when adding a `reserve` followed by a loop over a slice of source bytes:
```rust
pub fn append_packed_u32(dest: &mut Vec<u8>, src: &[u32], nbytes: usize) {
dest.reserve((src.len() + 1) * nbytes);
for val in src {
let n = dest.len() + nbytes;
dest.extend(val.to_le_bytes());
dest.truncate(n);
}
}
```
... the [compiler](https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=e0502909fe267e592ba37ede6e048281) isn't smart enough to eliminate the redundant capacity check inside the loop. Oh, well.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217808710
##########
parquet-variant/src/builder.rs:
##########
@@ -1317,7 +1414,15 @@ impl<'a> ObjectBuilder<'a> {
/// This is to ensure that the object is always finalized before its parent builder
/// is finalized.
impl Drop for ObjectBuilder<'_> {
- fn drop(&mut self) {}
+ fn drop(&mut self) {
+ // truncate the buffer if the `finish` method has not been called.
+ if !self.has_been_finished {
+ self.parent_state
+ .buffer()
+ .inner_mut()
+ .truncate(self.object_start_offset);
+ }
Review Comment:
Seems that in previous pr #7865, some logics want to cover that the metadata hasn't been rolled back in tests like `test_list_builder_to_object_builder_inner_no_finish`, do we need to roll back the `MetadataBuilder` here?
```
// The parent list should only contain the original values
list_builder.finish();
let (metadata, value) = builder.finish();
let metadata = VariantMetadata::try_new(&metadata).unwrap();
assert_eq!(metadata.len(), 1);
assert_eq!(&metadata[0], "name"); // not rolled back
```
I updated this into a separate commit, we can keep it or revert it easily.
IIUC, the `Metadata` can be rolled back because the object has not been written successfully, but not sure if there are any cases I did not follow here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217952918
##########
parquet-variant/src/builder.rs:
##########
@@ -506,6 +506,7 @@ enum ParentState<'a> {
metadata_builder: &'a mut MetadataBuilder,
fields: &'a mut IndexMap<u32, usize>,
field_name: &'a str,
+ object_start_offset: usize,
Review Comment:
Suggested a more understandable name (at least to me).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3104287150
🤖: Benchmark completed
<details><summary>Details</summary>
<p>
```
group 7899-avoid-extra-allocation-in-object-builder main
----- --------------------------------------------- ----
batch_json_string_to_variant json_list 8k string 1.00 28.4±0.11ms ? ?/sec 1.00 28.6±0.15ms ? ?/sec
batch_json_string_to_variant random_json(2633 bytes per document) 1.00 368.2±4.36ms ? ?/sec 1.06 389.3±6.43ms ? ?/sec
batch_json_string_to_variant repeated_struct 8k string 1.00 8.4±0.02ms ? ?/sec 1.02 8.5±0.02ms ? ?/sec
variant_get_primitive 1.00 1381.5±3.14µs ? ?/sec 1.00 1380.5±3.31µs ? ?/sec
```
</p>
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217940562
##########
parquet-variant/src/builder.rs:
##########
@@ -2357,8 +2673,8 @@ mod tests {
// Only the second attempt should appear in the final variant
let (metadata, value) = builder.finish();
let metadata = VariantMetadata::try_new(&metadata).unwrap();
- assert_eq!(metadata.len(), 1);
- assert_eq!(&metadata[0], "name"); // not rolled back
+ assert_eq!(metadata.len(), 1); // rolled back
+ assert_eq!(&metadata[0], "name");
Review Comment:
Hmm, why update this to "rolled back"? The metadata is same as before.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2218042453
##########
parquet-variant/src/builder.rs:
##########
@@ -1000,6 +1048,8 @@ impl<'a> ListBuilder<'a> {
// Get parent's buffer
let parent_buffer = self.parent_state.buffer();
+ // as object builder has been reused the parent buffer,
+ // we need to shift the offset by the starting offset of the parent object
Review Comment:
Good catch, because if we create a `ListBuilder` inside an `ObjectBuilder`, then we need do this shift, but after the last change, the comment here need to be moved to `ParentState::finish()`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2222164619
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
@scovich thanks for the reply, I've tried `let max_id = metadata_builder.field_names.len()` in commit(bdf1f2dda4693263d59c27d04439995b9c49138a), it will get a bigger header(the read/write logic is right), changed to `let max_id = metadata_builder.field_names.len() - 1` will get a bigger header size also, I'm figuring it now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3104945963
Ok, looks good to me. Thanks again. Let's address any additional comments as a follow on PR
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2214726707
##########
parquet-variant/src/builder.rs:
##########
@@ -1860,10 +2046,22 @@ mod tests {
let inner_object_variant = outer_object.field(2).unwrap();
let inner_object = inner_object_variant.as_object().unwrap();
- assert_eq!(inner_object.len(), 1);
+ assert_eq!(inner_object.len(), 3);
assert_eq!(inner_object.field_name(0).unwrap(), "b");
assert_eq!(inner_object.field(0).unwrap(), Variant::from("a"));
+ let inner_iner_object_variant_c = inner_object.field(1).unwrap();
+ let inner_inner_object_c = inner_iner_object_variant_c.as_object().unwrap();
+ assert_eq!(inner_inner_object_c.len(), 1);
+ assert_eq!(inner_inner_object_c.field_name(0).unwrap(), "aa");
+ assert_eq!(inner_inner_object_c.field(0).unwrap(), Variant::from("bb"));
+
+ let inner_iner_object_variant_d = inner_object.field(2).unwrap();
+ let inner_inner_object_d = inner_iner_object_variant_d.as_object().unwrap();
+ assert_eq!(inner_inner_object_d.len(), 1);
+ assert_eq!(inner_inner_object_d.field_name(0).unwrap(), "cc");
+ assert_eq!(inner_inner_object_d.field(0).unwrap(), Variant::from("dd"));
+
assert_eq!(outer_object.field_name(1).unwrap(), "b");
assert_eq!(outer_object.field(1).unwrap(), Variant::from(true));
}
Review Comment:
Okay, I will add more tests for this. Currently, the list inside the object depends on the `from_json` test, add a unit test for it in `builder.rs` is better, I'll add this.
Not sure if the tests like `test_xx_no_finishi()`(such as `test_object_builder_to_list_builder_inner_no_finish()`) are enough to cover the rollback logic?
We've called `drop` in the `test_xx_no_finish()` test, do we need to call `drop` if we add tests to cover the rollaback logic?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2214726707
##########
parquet-variant/src/builder.rs:
##########
@@ -1860,10 +2046,22 @@ mod tests {
let inner_object_variant = outer_object.field(2).unwrap();
let inner_object = inner_object_variant.as_object().unwrap();
- assert_eq!(inner_object.len(), 1);
+ assert_eq!(inner_object.len(), 3);
assert_eq!(inner_object.field_name(0).unwrap(), "b");
assert_eq!(inner_object.field(0).unwrap(), Variant::from("a"));
+ let inner_iner_object_variant_c = inner_object.field(1).unwrap();
+ let inner_inner_object_c = inner_iner_object_variant_c.as_object().unwrap();
+ assert_eq!(inner_inner_object_c.len(), 1);
+ assert_eq!(inner_inner_object_c.field_name(0).unwrap(), "aa");
+ assert_eq!(inner_inner_object_c.field(0).unwrap(), Variant::from("bb"));
+
+ let inner_iner_object_variant_d = inner_object.field(2).unwrap();
+ let inner_inner_object_d = inner_iner_object_variant_d.as_object().unwrap();
+ assert_eq!(inner_inner_object_d.len(), 1);
+ assert_eq!(inner_inner_object_d.field_name(0).unwrap(), "cc");
+ assert_eq!(inner_inner_object_d.field(0).unwrap(), Variant::from("dd"));
+
assert_eq!(outer_object.field_name(1).unwrap(), "b");
assert_eq!(outer_object.field(1).unwrap(), Variant::from(true));
}
Review Comment:
Okay, I will add more tests for this. Currently, the list inside the object depends on the `from_json` test, add a unit test for it in `builder.rs` is better, I'll add this.
Not sure if the tests like `test_xx_no_finishi()`(such as `test_object_builder_to_list_builder_inner_no_finish()`) is enough to cover the rollback logic?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217766357
##########
parquet-variant/src/builder.rs:
##########
@@ -598,6 +599,49 @@ impl ParentState<'_> {
}
}
}
+
+ // returns the beginning offset of buffer for the parent if it is object builder, else 0.
+ // for object builder will reuse the buffer from the parent, this is needed for `finish`
+ // which needs the relative offset from the current variant.
+ fn object_start_offset(&self) -> usize {
Review Comment:
This feature that reuse the parent buffer hasn't been implemented for `ListBuilder`. Will do it with a follow-up pr.
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
+
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write field IDs
+ for (&field_id, _) in &self.fields {
+ let id_bytes = (field_id as usize).to_le_bytes();
+ buffer[header_pos..header_pos + id_size as usize]
+ .copy_from_slice(&id_bytes[..id_size as usize]);
+ header_pos += id_size as usize;
+ }
- // Write the field offset array, followed by the value bytes
- let offsets = std::mem::take(&mut self.fields).into_values();
- parent_buffer.append_offset_array(offsets, Some(data_size), offset_size);
- parent_buffer.append_slice(self.buffer.inner());
- self.parent_state.finish(starting_offset);
+ // Write field offsets (adjusted for header)
+ for (_, &relative_offset) in &self.fields {
+ let offset_bytes = relative_offset.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&offset_bytes[..offset_size as usize]);
+ header_pos += offset_size as usize;
+ }
+
+ // Write data_size
+ let data_size_bytes = data_size.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&data_size_bytes[..offset_size as usize]);
+
+ let start_offset_shift = self.parent_state.object_start_offset();
+ self.parent_state
+ .finish(starting_offset - start_offset_shift);
Review Comment:
Yes, moving this logic to `ParentState::finish` is clearer. fixed.
##########
parquet-variant/src/builder.rs:
##########
@@ -1317,7 +1414,15 @@ impl<'a> ObjectBuilder<'a> {
/// This is to ensure that the object is always finalized before its parent builder
/// is finalized.
impl Drop for ObjectBuilder<'_> {
- fn drop(&mut self) {}
+ fn drop(&mut self) {
+ // truncate the buffer if the `finish` method has not been called.
+ if !self.has_been_finished {
+ self.parent_state
+ .buffer()
+ .inner_mut()
+ .truncate(self.object_start_offset);
+ }
Review Comment:
Seems that in previous pr #7865, some logics want to cover that the metadata hasn't been rolled back in tests like `test_list_builder_to_object_builder_inner_no_finish`, do we need to roll back the `MetadataBuilder` here?
I update this into a seperate commit, we can keep it or revert it easily.
IIUC, the `Metadata` can be rolled back because the object has not been written successfully, but not sure if there are any cases I did not follow here.
```
// The parent list should only contain the original values
list_builder.finish();
let (metadata, value) = builder.finish();
let metadata = VariantMetadata::try_new(&metadata).unwrap();
assert_eq!(metadata.len(), 1);
assert_eq!(&metadata[0], "name"); // not rolled back
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
Using the length of the metadata builder doesn't have a correctness problem, but it will have a tiny problem that will waste some space for the header. added in a separate commit.
##########
parquet-variant/src/builder.rs:
##########
@@ -598,6 +599,49 @@ impl ParentState<'_> {
}
}
}
+
+ // returns the beginning offset of buffer for the parent if it is object builder, else 0.
+ // for object builder will reuse the buffer from the parent, this is needed for `finish`
+ // which needs the relative offset from the current variant.
+ fn object_start_offset(&self) -> usize {
+ match self {
+ ParentState::Object {
+ object_start_offset,
+ ..
+ } => *object_start_offset,
+ _ => 0,
+ }
+ }
+
+ /// Return mutable references to the buffer and metadata builder that this
+ /// parent state is using.
+ fn buffer_and_metadata_builder(&mut self) -> (&mut ValueBuffer, &mut MetadataBuilder) {
+ match self {
+ ParentState::Variant {
+ buffer,
+ metadata_builder,
+ } => (buffer, metadata_builder),
+ ParentState::List {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ ParentState::Object {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
Review Comment:
addressed
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
Do you think it's ok to make this optimization a follow-up pr and add some benchmark for it?
##########
parquet-variant/src/builder.rs:
##########
@@ -598,6 +599,49 @@ impl ParentState<'_> {
}
}
}
+
+ // returns the beginning offset of buffer for the parent if it is object builder, else 0.
+ // for object builder will reuse the buffer from the parent, this is needed for `finish`
+ // which needs the relative offset from the current variant.
+ fn object_start_offset(&self) -> usize {
+ match self {
+ ParentState::Object {
+ object_start_offset,
+ ..
+ } => *object_start_offset,
+ _ => 0,
+ }
+ }
+
+ /// Return mutable references to the buffer and metadata builder that this
+ /// parent state is using.
+ fn buffer_and_metadata_builder(&mut self) -> (&mut ValueBuffer, &mut MetadataBuilder) {
+ match self {
+ ParentState::Variant {
+ buffer,
+ metadata_builder,
+ } => (buffer, metadata_builder),
+ ParentState::List {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ ParentState::Object {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ }
+ }
+
+ // return the offset of the underlying buffer at the time of calling this method.
+ fn buffer_current_offset(&self) -> usize {
+ match self {
+ ParentState::Variant { buffer, .. } => buffer.offset(),
+ ParentState::Object { buffer, .. } => buffer.offset(),
+ ParentState::List { buffer, .. } => buffer.offset(),
+ }
Review Comment:
This needs the signature changed to `buffer_current_offset(&mut self)`, not sure if this is ok?
changed to the first version
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2218441636
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
+ let id_size = int_size(max_id);
- let id_size = int_size(max_id as usize);
+ let parent_buffer = self.parent_state.buffer();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
let offset_size = int_size(data_size);
- // Get parent's buffer
- let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
- // Write header
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(
+ starting_offset..starting_offset,
+ std::iter::repeat_n(0u8, header_size),
+ );
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
Review Comment:
Fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2221275633
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
ok, will do it in a followup
##########
parquet-variant/src/builder.rs:
##########
@@ -1176,7 +1335,20 @@ impl<'a> ObjectBuilder<'a> {
/// This is to ensure that the object is always finalized before its parent builder
/// is finalized.
impl Drop for ObjectBuilder<'_> {
- fn drop(&mut self) {}
+ fn drop(&mut self) {
+ // Truncate the buffer if the `finish` method has not been called.
+ if !self.has_been_finished {
+ self.parent_state
+ .buffer()
+ .inner_mut()
+ .truncate(self.parent_offset_base);
Review Comment:
fixed
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
There will be no waste here, this is where I made a mistake before
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3077008532
@alamb Please help to review this when you have time, thanks.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2213460119
##########
parquet-variant/src/builder.rs:
##########
@@ -999,8 +1000,17 @@ impl<'a> ListBuilder<'a> {
let offset_size = int_size(data_size);
// Get parent's buffer
+ let offset_shift = match &self.parent_state {
Review Comment:
It might be nice if this was a function in ParentState, something like
```suggestion
let offset_shift = self.parent_state.object_start_offset();
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1038,28 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
+ object_start_offset: usize,
+ /// whether the object has been finished, the written content of the current object
+ /// will be truncated in `drop` if `has_been_finished` is false
+ has_been_finished: bool,
validate_unique_fields: bool,
/// Set of duplicate fields to report for errors
duplicate_fields: HashSet<u32>,
}
impl<'a> ObjectBuilder<'a> {
fn new(parent_state: ParentState<'a>, validate_unique_fields: bool) -> Self {
+ let start_offset = match &parent_state {
+ ParentState::Variant { buffer, .. } => buffer.offset(),
+ ParentState::List { buffer, .. } => buffer.offset(),
+ ParentState::Object { buffer, .. } => buffer.offset(),
+ };
Review Comment:
```suggestion
let start_offset = parent_state.buffer().offset();
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,38 +1230,96 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = match &self.parent_state {
+ ParentState::Variant {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::List {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::Object {
+ metadata_builder, ..
+ } => metadata_builder,
+ };
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
Review Comment:
As a follow on PR we can consider avoiding this extra splice somehow (by preallocating the size or something). Future work though
##########
parquet-variant/src/builder.rs:
##########
@@ -1064,20 +1084,58 @@ impl<'a> ObjectBuilder<'a> {
key: &str,
value: T,
) -> Result<(), ArrowError> {
- // Get metadata_builder from parent state
- let metadata_builder = self.parent_state.metadata_builder();
+ match &mut self.parent_state {
Review Comment:
Here is a proposal of how to avoid the duplication:
- https://github.com/klion26/arrow-rs/pull/1
##########
parquet-variant/src/builder.rs:
##########
@@ -955,13 +967,48 @@ impl<'a> ObjectBuilder<'a> {
// Returns validate_unique_fields because we can no longer reference self once this method returns.
fn parent_state<'b>(&'b mut self, key: &'b str) -> (ParentState<'b>, bool) {
- let state = ParentState::Object {
- buffer: &mut self.buffer,
- metadata_builder: self.parent_state.metadata_builder(),
- fields: &mut self.fields,
- field_name: key,
- };
- (state, self.validate_unique_fields)
+ let validate_unique_fields = self.validate_unique_fields;
+
+ match &mut self.parent_state {
Review Comment:
I think we can use the pattern in this pR: https://github.com/klion26/arrow-rs/pull/1
##########
parquet-variant/src/builder.rs:
##########
@@ -1860,10 +2046,22 @@ mod tests {
let inner_object_variant = outer_object.field(2).unwrap();
let inner_object = inner_object_variant.as_object().unwrap();
- assert_eq!(inner_object.len(), 1);
+ assert_eq!(inner_object.len(), 3);
assert_eq!(inner_object.field_name(0).unwrap(), "b");
assert_eq!(inner_object.field(0).unwrap(), Variant::from("a"));
+ let inner_iner_object_variant_c = inner_object.field(1).unwrap();
+ let inner_inner_object_c = inner_iner_object_variant_c.as_object().unwrap();
+ assert_eq!(inner_inner_object_c.len(), 1);
+ assert_eq!(inner_inner_object_c.field_name(0).unwrap(), "aa");
+ assert_eq!(inner_inner_object_c.field(0).unwrap(), Variant::from("bb"));
+
+ let inner_iner_object_variant_d = inner_object.field(2).unwrap();
+ let inner_inner_object_d = inner_iner_object_variant_d.as_object().unwrap();
+ assert_eq!(inner_inner_object_d.len(), 1);
+ assert_eq!(inner_inner_object_d.field_name(0).unwrap(), "cc");
+ assert_eq!(inner_inner_object_d.field(0).unwrap(), Variant::from("dd"));
+
assert_eq!(outer_object.field_name(1).unwrap(), "b");
assert_eq!(outer_object.field(1).unwrap(), Variant::from(true));
}
Review Comment:
I think we should also add tests for the rollback behavior (as in starting an ObjectBuilder but not calling finish)
Similar we should test a list builder rollback too
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,38 +1230,96 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = match &self.parent_state {
Review Comment:
it would be nice to put this into a method as well rather than an inline match statement
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,38 +1230,96 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = match &self.parent_state {
+ ParentState::Variant {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::List {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::Object {
+ metadata_builder, ..
+ } => metadata_builder,
+ };
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
+
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write field IDs
+ for (&field_id, _) in &self.fields {
+ let id_bytes = (field_id as usize).to_le_bytes();
+ buffer[header_pos..header_pos + id_size as usize]
+ .copy_from_slice(&id_bytes[..id_size as usize]);
+ header_pos += id_size as usize;
+ }
- // Write the field offset array, followed by the value bytes
- let offsets = std::mem::take(&mut self.fields).into_values();
- parent_buffer.append_offset_array(offsets, Some(data_size), offset_size);
- parent_buffer.append_slice(self.buffer.inner());
- self.parent_state.finish(starting_offset);
+ // Write field offsets (adjusted for header)
+ for (_, &relative_offset) in &self.fields {
+ let offset_bytes = relative_offset.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&offset_bytes[..offset_size as usize]);
+ header_pos += offset_size as usize;
+ }
+
+ // Write data_size
+ let data_size_bytes = data_size.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&data_size_bytes[..offset_size as usize]);
+
+ let start_offset_shift = match &self.parent_state {
Review Comment:
here is another place we could use the method and avoid an inline match
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3089923144
🤖: Benchmark completed
<details><summary>Details</summary>
<p>
```
group 7899-avoid-extra-allocation-in-object-builder main
----- --------------------------------------------- ----
batch_json_string_to_variant json_list 8k string 1.00 27.9±0.10ms ? ?/sec 1.03 28.7±0.11ms ? ?/sec
batch_json_string_to_variant random_json(2633 bytes per document) 1.00 364.7±8.44ms ? ?/sec 1.08 392.4±6.39ms ? ?/sec
batch_json_string_to_variant repeated_struct 8k string 1.01 8.6±0.02ms ? ?/sec 1.00 8.6±0.03ms ? ?/sec
variant_get_primitive 1.00 1368.4±16.34µs ? ?/sec 1.01 1375.4±8.13µs ? ?/sec
```
</p>
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2222089981
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
Eek! Sorry, that should be `metadata.len() - 1`, not `fields.len() - 1`!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217915311
##########
parquet-variant/src/builder.rs:
##########
@@ -1118,8 +1181,8 @@ impl<'a> ObjectBuilder<'a> {
/// Finalizes this object and appends it to its parent, which otherwise remains unmodified.
pub fn finish(mut self) -> Result<(), ArrowError> {
- let metadata_builder = self.parent_state.metadata_builder();
if self.validate_unique_fields && !self.duplicate_fields.is_empty() {
+ let metadata_builder = self.parent_state.metadata_builder();
Review Comment:
Hm? Why move `metadata_builder` inside?
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1078,29 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
+ object_start_offset: usize,
Review Comment:
```suggestion
parent_offset_base: usize,
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1000,6 +1048,8 @@ impl<'a> ListBuilder<'a> {
// Get parent's buffer
let parent_buffer = self.parent_state.buffer();
+ // as object builder has been reused the parent buffer,
+ // we need to shift the offset by the starting offset of the parent object
Review Comment:
I don't get it why put the comment here, seems `ListBuilder.finish` hasn't been updated.
##########
parquet-variant/src/builder.rs:
##########
@@ -506,6 +506,7 @@ enum ParentState<'a> {
metadata_builder: &'a mut MetadataBuilder,
fields: &'a mut IndexMap<u32, usize>,
field_name: &'a str,
+ object_start_offset: usize,
Review Comment:
```suggestion
parent_offset_base: usize,
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1078,29 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
Review Comment:
Style suggestion, it'd be better just following existing doc style.
```suggestion
/// The starting offset in the parent's buffer where this object starts
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1078,29 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
+ object_start_offset: usize,
+ /// the starting offset in the parent's metadata buffer where this object starts
+ /// used to truncate the written fields in `drop` if the current object has not been finished
+ object_meta_start_offset: usize,
Review Comment:
```suggestion
parent_metadata_offset_base: usize,
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
+ let id_size = int_size(max_id);
- let id_size = int_size(max_id as usize);
+ let parent_buffer = self.parent_state.buffer();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
Review Comment:
Hmm, so we assume that no other object was appended at the same time? If we create two object builders and they insert into the parent buffer in an interleaved manner? Won't be the base offset (object start offset) same for them?
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1078,29 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
Review Comment:
Similar style issues on other comment/doc.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217933884
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
+ let id_size = int_size(max_id);
- let id_size = int_size(max_id as usize);
+ let parent_buffer = self.parent_state.buffer();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
let offset_size = int_size(data_size);
- // Get parent's buffer
- let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
- // Write header
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(
+ starting_offset..starting_offset,
+ std::iter::repeat_n(0u8, header_size),
+ );
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
Review Comment:
This is basically `append_header` did, right? Maybe we can also extract to a function instead of inline here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217931769
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
Review Comment:
Hmm, honestly I didn't get what this comment trying to say. And the `max_id` is same as the length of `field_names` exactly?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2216465127
##########
parquet-variant/src/builder.rs:
##########
@@ -598,6 +599,49 @@ impl ParentState<'_> {
}
}
}
+
+ // returns the beginning offset of buffer for the parent if it is object builder, else 0.
+ // for object builder will reuse the buffer from the parent, this is needed for `finish`
+ // which needs the relative offset from the current variant.
+ fn object_start_offset(&self) -> usize {
+ match self {
+ ParentState::Object {
+ object_start_offset,
+ ..
+ } => *object_start_offset,
+ _ => 0,
+ }
+ }
+
+ /// Return mutable references to the buffer and metadata builder that this
+ /// parent state is using.
+ fn buffer_and_metadata_builder(&mut self) -> (&mut ValueBuffer, &mut MetadataBuilder) {
+ match self {
+ ParentState::Variant {
+ buffer,
+ metadata_builder,
+ } => (buffer, metadata_builder),
+ ParentState::List {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ ParentState::Object {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
Review Comment:
I _think_ rust allows this:
```suggestion
ParentState::Variant {
buffer,
metadata_builder,
} |
ParentState::List {
buffer,
metadata_builder,
..
} |
ParentState::Object {
buffer,
metadata_builder,
..
} => (buffer, metadata_builder),
```
Not clear whether that's better or worse than the current code.
I'm also not sure how it would `fmt`.
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
+
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write field IDs
+ for (&field_id, _) in &self.fields {
+ let id_bytes = (field_id as usize).to_le_bytes();
+ buffer[header_pos..header_pos + id_size as usize]
+ .copy_from_slice(&id_bytes[..id_size as usize]);
+ header_pos += id_size as usize;
+ }
- // Write the field offset array, followed by the value bytes
- let offsets = std::mem::take(&mut self.fields).into_values();
- parent_buffer.append_offset_array(offsets, Some(data_size), offset_size);
- parent_buffer.append_slice(self.buffer.inner());
- self.parent_state.finish(starting_offset);
+ // Write field offsets (adjusted for header)
+ for (_, &relative_offset) in &self.fields {
Review Comment:
```suggestion
for relative_offset in self.fields.values() {
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
+
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write field IDs
+ for (&field_id, _) in &self.fields {
+ let id_bytes = (field_id as usize).to_le_bytes();
+ buffer[header_pos..header_pos + id_size as usize]
+ .copy_from_slice(&id_bytes[..id_size as usize]);
+ header_pos += id_size as usize;
+ }
- // Write the field offset array, followed by the value bytes
- let offsets = std::mem::take(&mut self.fields).into_values();
- parent_buffer.append_offset_array(offsets, Some(data_size), offset_size);
- parent_buffer.append_slice(self.buffer.inner());
- self.parent_state.finish(starting_offset);
+ // Write field offsets (adjusted for header)
+ for (_, &relative_offset) in &self.fields {
+ let offset_bytes = relative_offset.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&offset_bytes[..offset_size as usize]);
+ header_pos += offset_size as usize;
+ }
+
+ // Write data_size
+ let data_size_bytes = data_size.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&data_size_bytes[..offset_size as usize]);
+
+ let start_offset_shift = self.parent_state.object_start_offset();
+ self.parent_state
+ .finish(starting_offset - start_offset_shift);
Review Comment:
Why make the caller of `ParentState::finish` extract the start offset? Seems like parent state can do that more easily and reliably on its own?
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
Review Comment:
aside: I'd be very impressed if the compiler is smart enough to optimize away the allocation in `vec![0u8; header_size].into_iter()`, which would potentially cause the above to run slower than the current code.
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
Review Comment:
Alternatively -- that small allocation apparently isn't hurting performance. What if we create the temp vec with initial capacity of `header_size` and then populate it with the actual header info, field ids, and offsets before splicing it in. That way, an incorrect `header_size` calculation would not impact correctness:
```rust
let mut bytes_to_splice = Vec::with_capacity(header_size);
bytes_to_splice.push(header_byte);
if is_large {
bytes_to_splice.extend((num_fields as u32).to_le_bytes());
} else {
bytes_to_splice.push(num_fields as u8);
}
for &field_id in self.fields.keys() {
bytes_to_splice.extend(field_id.to_le_bytes().into_iter().take(id_size));
}
for &offset in self.fields.values() {
bytes_to_splice.extend((offset as u32).to_le_bytes().into_iter().take(offset_size));
}
bytes_to_splice.extend((data_size as u32).to_le_bytes().into_iter().take(offset_size));
buffer.splice(starting_offset..starting_offset, bytes_to_splice);
```
##########
parquet-variant/src/builder.rs:
##########
@@ -598,6 +599,49 @@ impl ParentState<'_> {
}
}
}
+
+ // returns the beginning offset of buffer for the parent if it is object builder, else 0.
+ // for object builder will reuse the buffer from the parent, this is needed for `finish`
+ // which needs the relative offset from the current variant.
+ fn object_start_offset(&self) -> usize {
Review Comment:
Doesn't variant array also have a starting offset?
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
One thing I don't love about this approach is the independent calculation of the splice size vs. the bytes that actually get inserted. If they ever disagreed... badness as the insertions underflow or overflow the splice.
Ideally, we could produce an iterator that emits the desired bytes, and the splice itself can guarantee correct behavior. But for that to work the iterator would need to provide an accurate lower bound, so which rules out `std::iter::from_fn`. Even if we did craft a custom iterator, computing its lower bound would basically be this same calculation all over again. We could also chain together a bunch of iterators, which preserves the lower bound, but somehow I doubt that would be efficient.
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
+
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write field IDs
+ for (&field_id, _) in &self.fields {
Review Comment:
```suggestion
for field_id in self.fields.keys() {
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1317,7 +1414,15 @@ impl<'a> ObjectBuilder<'a> {
/// This is to ensure that the object is always finalized before its parent builder
/// is finalized.
impl Drop for ObjectBuilder<'_> {
- fn drop(&mut self) {}
+ fn drop(&mut self) {
+ // truncate the buffer if the `finish` method has not been called.
+ if !self.has_been_finished {
+ self.parent_state
+ .buffer()
+ .inner_mut()
+ .truncate(self.object_start_offset);
+ }
Review Comment:
While we're at it, we should truncate the `MetadataBuilder` back to the size it had when we started, to clean up any new field ids the failed builder might have created.
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
aside: Rather than pay a traversal over the list of fields, I would just use the metadata builder's current length as a _very_ cheap to compute upper bound. It will almost always be a tight upper bound as well -- it would take a pretty carefully crafted object to use only the early/small field ids of a large dictionary, such that the dictionary length needs more encoding bytes than the largest field ids of this object.
##########
parquet-variant/src/builder.rs:
##########
@@ -598,6 +599,49 @@ impl ParentState<'_> {
}
}
}
+
+ // returns the beginning offset of buffer for the parent if it is object builder, else 0.
+ // for object builder will reuse the buffer from the parent, this is needed for `finish`
+ // which needs the relative offset from the current variant.
+ fn object_start_offset(&self) -> usize {
+ match self {
+ ParentState::Object {
+ object_start_offset,
+ ..
+ } => *object_start_offset,
+ _ => 0,
+ }
+ }
+
+ /// Return mutable references to the buffer and metadata builder that this
+ /// parent state is using.
+ fn buffer_and_metadata_builder(&mut self) -> (&mut ValueBuffer, &mut MetadataBuilder) {
+ match self {
+ ParentState::Variant {
+ buffer,
+ metadata_builder,
+ } => (buffer, metadata_builder),
+ ParentState::List {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ ParentState::Object {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ }
+ }
+
+ // return the offset of the underlying buffer at the time of calling this method.
+ fn buffer_current_offset(&self) -> usize {
+ match self {
+ ParentState::Variant { buffer, .. } => buffer.offset(),
+ ParentState::Object { buffer, .. } => buffer.offset(),
+ ParentState::List { buffer, .. } => buffer.offset(),
+ }
Review Comment:
As above, can reduce redundancy by
```suggestion
match self {
ParentState::Variant { buffer, .. }
| ParentState::Object { buffer, .. }
| ParentState::List { buffer, .. } => buffer.offset(),
}
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
Review Comment:
Can avoid even this allocation:
```suggestion
buffer.splice(starting_offset..starting_offset, std::iter::repeat_n(0u8, header_size));
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
... but again, I worry that wrapping up all those for-loops inside an iterator for direct splicing will turn out to be a lot slower than the splice-then-overwrite approach the code currently takes.
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
Something like might _almost_ work?
```rust
let field_ids = self.fields.keys().flat_map(|field_id| {
(field_id as usize).to_le_bytes().into_iter().take(id_size)
});
let offsets = self.fields.values().flat_map(|offset| {
offset.to_le_bytes().into_iter().take(offset_size)
});
let num_fields = num_fields.to_le_bytes().take(if is_large 4 else 1);
let header_and_num_fields = std::iter::once(header_byte).chain(num_fields);
let field_ids_and_offsets = field_ids.chain(offsets);
let bytes_to_splice = header_and_num_fields.chain(field_ids_and_offsets);
buffer.splice(starting_offset..starting_offset, bytes_to_splice);
```
... but unfortunately `Iterator::flat_map` does _not_ (honestly, cannot) compute an accurate lower bound size hint. So the `splice` call would end up having to allocate an internal temp buffer.
##########
parquet-variant/src/builder.rs:
##########
@@ -598,6 +599,49 @@ impl ParentState<'_> {
}
}
}
+
+ // returns the beginning offset of buffer for the parent if it is object builder, else 0.
+ // for object builder will reuse the buffer from the parent, this is needed for `finish`
+ // which needs the relative offset from the current variant.
+ fn object_start_offset(&self) -> usize {
+ match self {
+ ParentState::Object {
+ object_start_offset,
+ ..
+ } => *object_start_offset,
+ _ => 0,
+ }
+ }
+
+ /// Return mutable references to the buffer and metadata builder that this
+ /// parent state is using.
+ fn buffer_and_metadata_builder(&mut self) -> (&mut ValueBuffer, &mut MetadataBuilder) {
+ match self {
+ ParentState::Variant {
+ buffer,
+ metadata_builder,
+ } => (buffer, metadata_builder),
+ ParentState::List {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ ParentState::Object {
+ buffer,
+ metadata_builder,
+ ..
+ } => (buffer, metadata_builder),
+ }
+ }
+
+ // return the offset of the underlying buffer at the time of calling this method.
+ fn buffer_current_offset(&self) -> usize {
+ match self {
+ ParentState::Variant { buffer, .. } => buffer.offset(),
+ ParentState::Object { buffer, .. } => buffer.offset(),
+ ParentState::List { buffer, .. } => buffer.offset(),
+ }
Review Comment:
Actually... we can just invoke `ParentState::buffer`?
```suggestion
self.buffer().offset()
```
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
I just realized -- a custom iterator that computes its size hint is still safer than the current code, because an incorrect size hint won't corrupt any data. It will just require extra allocations and/or byte shifting. There's still the question of performance tho. If it's drastically slower the extra safety probably wouldn't be worth it.
Another possibility is to take a hybrid approach -- rely on `Iterator::chain` for most of the heavy lifting, but define a custom iterator for emitting offset/field_id arrays:
```rust
let num_fields = num_fields.to_le_bytes().take(if is_large 4 else 1);
let header_and_num_fields = std::iter::once(header_byte).chain(num_fields);
let field_ids = PackedU32Iterator::new(id_size, self.fields.keys().copied());
let offsets = PackedU32Iterator::new(offset_size, self.fields.values().map(|offset| *offset as u32));
let field_ids_and_offsets = field_ids.chain(offsets);
let bytes_to_splice = header_and_num_fields.chain(field_ids_and_offsets);
buffer.splice(starting_offset..starting_offset, bytes_to_splice);
```
<details>
<summary>PackedU32Iterator</summary>
```rust
struct PackedU32Iterator<T: impl Iterator<Item = [u8; 4]>> {
packed_bytes: usize,
iterator: T,
current_item: [u8; 4],
current_byte: usize, // 0..3
}
impl<T: impl Iterator<Item = [u8; 4]>> PackedU32Iterator<T> {
fn new(packed_bytes: usize, iterator: T) -> Self {
// eliminate corner cases in `next` by initializing with a fake already-consumed "first" item
Self {
packed_bytes,
iterator,
current_item: [0; 4],
current_byte: packed_bytes,
}
}
}
impl<T: impl Iterator<Item = [u8; 4]>> Iterator for PackedU32Iterator<T> {
fn size_hint(&self) -> (usize, Option<usize>) {
let lower = (packed_bytes - current_byte) + packed_bytes * iterator.size_hint().0;
(lower, None)
}
fn next(&mut self) -> Option<u8> {
if self.current_byte >= self.packed_bytes {
let Some(next_item) = self.iterator.next() else {
return None;
};
self.current_item = next_item;
self.current_byte = 0;
}
let rval = self.current_item[self.current_byte];
self.current_byte += 1;
Some(rval)
}
}
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2221326885
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
change current logic to `let max_id = self.fields.len() - 1` will fail the `parquet_varient_json/from_json#test_json_to_variant_object_very_large` test, I'm looking into it.
The error message `InvalidArgumentError("field names not sorted")`
I think this does not affect the current pr, I'll do it in the follow-up after figuring out why the tests failed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2220120562
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
Why would it waste space? With high probability, the largest field id in the object will take the same number of bytes to encode as `self.fields.len() - 1` (the highest field id in the dictionary), so using the latter shouldn't change anything?
##########
parquet-variant/src/builder.rs:
##########
@@ -1176,7 +1335,20 @@ impl<'a> ObjectBuilder<'a> {
/// This is to ensure that the object is always finalized before its parent builder
/// is finalized.
impl Drop for ObjectBuilder<'_> {
- fn drop(&mut self) {}
+ fn drop(&mut self) {
+ // Truncate the buffer if the `finish` method has not been called.
+ if !self.has_been_finished {
+ self.parent_state
+ .buffer()
+ .inner_mut()
+ .truncate(self.parent_offset_base);
Review Comment:
now that we have two offset bases, should we rename this one as `parent_value_offset_base` for clarity?
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
Or try the other approach that populates the tmp vec with non-zero bytes before splicing it into the main buffer? That's a lot simpler than this iterator-based suggestion, and likely performs better too.
##########
parquet-variant/src/builder.rs:
##########
@@ -2253,8 +2620,7 @@ mod tests {
// The original builder should be unchanged
let (metadata, value) = builder.finish();
let metadata = VariantMetadata::try_new(&metadata).unwrap();
- assert_eq!(metadata.len(), 1);
- assert_eq!(&metadata[0], "name"); // not rolled back
+ assert!(metadata.is_empty()); // rolled back
Review Comment:
yay! 🎉
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3077162769
The test in `builder.rs` completed successfully, will investigate why CI fails.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2216382026
##########
parquet-variant/src/builder.rs:
##########
@@ -1317,7 +1414,15 @@ impl<'a> ObjectBuilder<'a> {
/// This is to ensure that the object is always finalized before its parent builder
/// is finalized.
impl Drop for ObjectBuilder<'_> {
- fn drop(&mut self) {}
+ fn drop(&mut self) {
Review Comment:
❤️
##########
parquet-variant/src/builder.rs:
##########
@@ -1860,10 +2046,22 @@ mod tests {
let inner_object_variant = outer_object.field(2).unwrap();
let inner_object = inner_object_variant.as_object().unwrap();
- assert_eq!(inner_object.len(), 1);
+ assert_eq!(inner_object.len(), 3);
assert_eq!(inner_object.field_name(0).unwrap(), "b");
assert_eq!(inner_object.field(0).unwrap(), Variant::from("a"));
+ let inner_iner_object_variant_c = inner_object.field(1).unwrap();
+ let inner_inner_object_c = inner_iner_object_variant_c.as_object().unwrap();
+ assert_eq!(inner_inner_object_c.len(), 1);
+ assert_eq!(inner_inner_object_c.field_name(0).unwrap(), "aa");
+ assert_eq!(inner_inner_object_c.field(0).unwrap(), Variant::from("bb"));
+
+ let inner_iner_object_variant_d = inner_object.field(2).unwrap();
+ let inner_inner_object_d = inner_iner_object_variant_d.as_object().unwrap();
+ assert_eq!(inner_inner_object_d.len(), 1);
+ assert_eq!(inner_inner_object_d.field_name(0).unwrap(), "cc");
+ assert_eq!(inner_inner_object_d.field(0).unwrap(), Variant::from("dd"));
+
assert_eq!(outer_object.field_name(1).unwrap(), "b");
assert_eq!(outer_object.field(1).unwrap(), Variant::from(true));
}
Review Comment:
After reviewing the tests, I agree that the existing tests are sufficient
https://github.com/apache/arrow-rs/blob/0fecaa0869260b014235ef527462b07a45ffa0d2/parquet-variant/src/builder.rs#L2837-L2918
I also verified test coverage with
```shell
cargo llvm-cov --html test -p parquet-variant
```
And it is indeed covered:
<img width="950" height="372" alt="Screenshot 2025-07-18 at 11 58 35 AM" src="https://github.com/user-attachments/assets/900d99d9-fe47-40bc-b14e-c19eefc9e0ee" />
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
Review Comment:
TIL: `VEC::splice`
https://doc.rust-lang.org/std/vec/struct.Vec.html#method.splice
Nice
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3086429057
@alamb Thanks for the detailed review, will adressed them soon.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2212134518
##########
parquet-variant/src/builder.rs:
##########
@@ -1064,20 +1084,58 @@ impl<'a> ObjectBuilder<'a> {
key: &str,
value: T,
) -> Result<(), ArrowError> {
- // Get metadata_builder from parent state
- let metadata_builder = self.parent_state.metadata_builder();
+ match &mut self.parent_state {
Review Comment:
same as below
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2218045675
##########
parquet-variant/src/builder.rs:
##########
@@ -1118,8 +1181,8 @@ impl<'a> ObjectBuilder<'a> {
/// Finalizes this object and appends it to its parent, which otherwise remains unmodified.
pub fn finish(mut self) -> Result<(), ArrowError> {
- let metadata_builder = self.parent_state.metadata_builder();
if self.validate_unique_fields && !self.duplicate_fields.is_empty() {
+ let metadata_builder = self.parent_state.metadata_builder();
Review Comment:
This was intended to avoid the double mutable reference problem, but it's not a problem after the implementation has changed. I can revert this if needed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2222141902
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
Review Comment:
I also think we can mitigate the danger of independent size calculation with testing.
I like the idea of going with the approach in this PR (which is already pretty large)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2222164619
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
@scovich thanks for the reply, I've tried `let max_id = metadata_builder.field_names.len()` in commit(bdf1f2dda4693263d59c27d04439995b9c49138a), it will get a bigger header(the read/write logic is right), changed to `let max_id = metadata_builder.field_names.len() - 1` will get a bigger header size also, From the log above, we can see, `metadata_builder.field_names.len() - 1` may be bigger than `max_id` because we'll reuse the parent's IndexSet for the `filed_names`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2222164619
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
@scovich thanks for the reply, I've tried `let max_id = metadata_builder.field_names.len()` in commit(bdf1f2dda4693263d59c27d04439995b9c49138a), it will get a bigger header(the read/write logic is right), changed to `let max_id = metadata_builder.field_names.len() - 1` will get a bigger header size also. From the log above, we can see, `metadata_builder.field_names.len() - 1` may be bigger than `max_id` because we'll reuse the parent's IndexSet for the `field_names`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2222151341
##########
parquet-variant/src/builder.rs:
##########
@@ -1118,8 +1181,8 @@ impl<'a> ObjectBuilder<'a> {
/// Finalizes this object and appends it to its parent, which otherwise remains unmodified.
pub fn finish(mut self) -> Result<(), ArrowError> {
- let metadata_builder = self.parent_state.metadata_builder();
if self.validate_unique_fields && !self.duplicate_fields.is_empty() {
+ let metadata_builder = self.parent_state.metadata_builder();
Review Comment:
I reverted this change in 19bb544be4 to keep the diff cleaner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3099772424
🤖 `./gh_compare_arrow.sh` [Benchmark Script](https://github.com/alamb/datafusion-benchmarking/blob/main/gh_compare_arrow.sh) Running
Linux aal-dev 6.11.0-1016-gcp #16~24.04.1-Ubuntu SMP Wed May 28 02:40:52 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Comparing 7899-avoid-extra-allocation-in-object-builder (f0d35de7ddea94d03c9b8808c077cce6a7045dc9) to 03a837e883323ef7e3294f0805c9e1cadd3963b8 [diff](https://github.com/apache/arrow-rs/compare/03a837e883323ef7e3294f0805c9e1cadd3963b8..f0d35de7ddea94d03c9b8808c077cce6a7045dc9)
BENCH_NAME=variant_kernels
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental --bench variant_kernels
BENCH_FILTER=
BENCH_BRANCH_NAME=7899-avoid-extra-allocation-in-object-builder
Results will be posted here when complete
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2221326885
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
change current logic to `let max_id = self.fields.len() - 1` will fail the `parquet_varient_json/from_json#test_json_to_variant_object_very_large` test, I'm looking into it.
I think this does not affect the current pr, I'll do it in the follow-up after figuring out why the tests failed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2214909965
##########
parquet-variant/src/builder.rs:
##########
@@ -955,13 +967,48 @@ impl<'a> ObjectBuilder<'a> {
// Returns validate_unique_fields because we can no longer reference self once this method returns.
fn parent_state<'b>(&'b mut self, key: &'b str) -> (ParentState<'b>, bool) {
- let state = ParentState::Object {
- buffer: &mut self.buffer,
- metadata_builder: self.parent_state.metadata_builder(),
- fields: &mut self.fields,
- field_name: key,
- };
- (state, self.validate_unique_fields)
+ let validate_unique_fields = self.validate_unique_fields;
+
+ match &mut self.parent_state {
Review Comment:
Fixed, it becomes cleaner now.
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1038,28 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
+ object_start_offset: usize,
+ /// whether the object has been finished, the written content of the current object
+ /// will be truncated in `drop` if `has_been_finished` is false
+ has_been_finished: bool,
validate_unique_fields: bool,
/// Set of duplicate fields to report for errors
duplicate_fields: HashSet<u32>,
}
impl<'a> ObjectBuilder<'a> {
fn new(parent_state: ParentState<'a>, validate_unique_fields: bool) -> Self {
+ let start_offset = match &parent_state {
+ ParentState::Variant { buffer, .. } => buffer.offset(),
+ ParentState::List { buffer, .. } => buffer.offset(),
+ ParentState::Object { buffer, .. } => buffer.offset(),
+ };
Review Comment:
Tried this way, but it needs to change the `parent_state` to mutable. Added a function to retrieve the current offset of the buffer.
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,38 +1230,96 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = match &self.parent_state {
+ ParentState::Variant {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::List {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::Object {
+ metadata_builder, ..
+ } => metadata_builder,
+ };
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
Review Comment:
filed an issue(#7960) to trace this.
##########
parquet-variant/src/builder.rs:
##########
@@ -1064,20 +1084,58 @@ impl<'a> ObjectBuilder<'a> {
key: &str,
value: T,
) -> Result<(), ArrowError> {
- // Get metadata_builder from parent state
- let metadata_builder = self.parent_state.metadata_builder();
+ match &mut self.parent_state {
Review Comment:
Fixed
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,38 +1230,96 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = match &self.parent_state {
+ ParentState::Variant {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::List {
+ metadata_builder, ..
+ } => metadata_builder,
+ ParentState::Object {
+ metadata_builder, ..
+ } => metadata_builder,
+ };
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
+
+ // Write header at the original start position
+ let mut header_pos = starting_offset;
+
+ // Write header byte
let header = object_header(is_large, id_size, offset_size);
- parent_buffer.append_header(header, is_large, num_fields);
+ buffer[header_pos] = header;
+ header_pos += 1;
+
+ // Write number of fields
+ if is_large {
+ buffer[header_pos..header_pos + 4].copy_from_slice(&(num_fields as u32).to_le_bytes());
+ header_pos += 4;
+ } else {
+ buffer[header_pos] = num_fields as u8;
+ header_pos += 1;
+ }
- // Write field IDs (sorted order)
- let ids = self.fields.keys().map(|id| *id as usize);
- parent_buffer.append_offset_array(ids, None, id_size);
+ // Write field IDs
+ for (&field_id, _) in &self.fields {
+ let id_bytes = (field_id as usize).to_le_bytes();
+ buffer[header_pos..header_pos + id_size as usize]
+ .copy_from_slice(&id_bytes[..id_size as usize]);
+ header_pos += id_size as usize;
+ }
- // Write the field offset array, followed by the value bytes
- let offsets = std::mem::take(&mut self.fields).into_values();
- parent_buffer.append_offset_array(offsets, Some(data_size), offset_size);
- parent_buffer.append_slice(self.buffer.inner());
- self.parent_state.finish(starting_offset);
+ // Write field offsets (adjusted for header)
+ for (_, &relative_offset) in &self.fields {
+ let offset_bytes = relative_offset.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&offset_bytes[..offset_size as usize]);
+ header_pos += offset_size as usize;
+ }
+
+ // Write data_size
+ let data_size_bytes = data_size.to_le_bytes();
+ buffer[header_pos..header_pos + offset_size as usize]
+ .copy_from_slice(&data_size_bytes[..offset_size as usize]);
+
+ let start_offset_shift = match &self.parent_state {
Review Comment:
fixed
##########
parquet-variant/src/builder.rs:
##########
@@ -999,8 +1000,17 @@ impl<'a> ListBuilder<'a> {
let offset_size = int_size(data_size);
// Get parent's buffer
+ let offset_shift = match &self.parent_state {
Review Comment:
Fixed
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,38 +1230,96 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = match &self.parent_state {
Review Comment:
fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3089911780
🤖 `./gh_compare_arrow.sh` [Benchmark Script](https://github.com/alamb/datafusion-benchmarking/blob/main/gh_compare_arrow.sh) Running
Linux aal-dev 6.11.0-1016-gcp #16~24.04.1-Ubuntu SMP Wed May 28 02:40:52 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Comparing 7899-avoid-extra-allocation-in-object-builder (0fecaa0869260b014235ef527462b07a45ffa0d2) to 99eb1bc92b129b0431cf79292cfa6361bb74cfc4 [diff](https://github.com/apache/arrow-rs/compare/99eb1bc92b129b0431cf79292cfa6361bb74cfc4..0fecaa0869260b014235ef527462b07a45ffa0d2)
BENCH_NAME=variant_kernels
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental --bench variant_kernels
BENCH_FILTER=
BENCH_BRANCH_NAME=7899-avoid-extra-allocation-in-object-builder
Results will be posted here when complete
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217431963
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
Review Comment:
FYI, I think we can improve the performance of appending packed `u32` values to a `Vec<u8>`. The following code:
```rust
pub fn append_bytes_brute2(dest: &mut Vec<u8>, src: u32, nbytes: NumBytes) {
let n = dest.len() + nbytes as usize;
dest.extend(src.to_le_bytes());
dest.truncate(n);
}
```
... unconditionally adds all four bytes and then truncates the vector to the desired length. This works because (a) it's a single machine instruction to copy the four LE bytes of a `u32` to a memory location; and (b) `truncate` is dirt cheap (conditional move that doesn't break processor pipelines the way a branch would).
Result: Code that should perform the same regardless of the number of bytes we encode the `u32` as, with only a single branch to check for vector capacity.
<details>
The above [compiles](https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=c4e3f95d39ad58148435d55ff7095a3a) to the following assembly code:
```asm
playground::append_packed_u32:
;; set up stack frame (not relevant in practice due to inlining)
...
movq (%rdi), %rcx ; dest capacity
movq 16(%rdi), %rbx ; dest len
subq %rbx, %rcx ; calculate available capacity
movq %rbx, %rax
cmpq $3, %rcx ; if insufficient capacity...
jbe .LBB2_1 ; ... then `reserve` more
.LBB2_2:
addq %rdx, %rbx ; add nbytes to len (truncate arg)
movq 8(%rdi), %rcx ; dest data pointer
movl %esi, (%rcx,%rax) ; store all four bytes of src in the vector
addq $4, %rax ; increase len by 4 (u32 size)
cmpq %rax, %rbx ; if new len is bigger than truncate arg...
cmovbq %rbx, %rax ; ... then truncate len
movq %rax, 16(%rdi) ; write back the updated dest len
;; tear down stack frame
...
retq
.LBB2_1:
;; call prologue
...
callq alloc::raw_vec::RawVecInner<A>::reserve::do_reserve_and_handle
;; call epilogue
...
jmp .LBB2_2
```
The one bummer is, when adding a `reserve` followed by a loop over a slice of source bytes:
```rust
pub fn append_packed_u32(dest: &mut Vec<u8>, src: &[u32], nbytes: usize) {
dest.reserve((src.len() + 1) * nbytes);
for val in src {
let n = dest.len() + nbytes;
dest.extend(val.to_le_bytes());
dest.truncate(n);
}
}
```
... the [compiler](https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=e0502909fe267e592ba37ede6e048281) isn't smart enough to eliminate the redundant capacity check inside the loop. Oh, well.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3082416040
@alamb thank you! I've rebased on the main branch, and hardened the nestes object test.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2209376279
##########
parquet-variant/src/builder.rs:
##########
@@ -955,13 +967,48 @@ impl<'a> ObjectBuilder<'a> {
// Returns validate_unique_fields because we can no longer reference self once this method returns.
fn parent_state<'b>(&'b mut self, key: &'b str) -> (ParentState<'b>, bool) {
- let state = ParentState::Object {
- buffer: &mut self.buffer,
- metadata_builder: self.parent_state.metadata_builder(),
- fields: &mut self.fields,
- field_name: key,
- };
- (state, self.validate_unique_fields)
+ let validate_unique_fields = self.validate_unique_fields;
+
+ match &mut self.parent_state {
Review Comment:
Did not find a better solution for this. I can change this if there is a better solution.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2217431963
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
-
let id_size = int_size(max_id as usize);
- let offset_size = int_size(data_size);
- // Get parent's buffer
let parent_buffer = self.parent_state.buffer();
- let starting_offset = parent_buffer.offset();
+ let current_offset = parent_buffer.offset();
+ // current object starts from `object_start_offset`
+ let data_size = current_offset - self.object_start_offset;
+ let offset_size = int_size(data_size);
- // Write header
+ let num_fields = self.fields.len();
+ let is_large = num_fields > u8::MAX as usize;
+
+ let header_size = 1 + // header byte
+ (if is_large { 4 } else { 1 }) + // num_fields
+ (num_fields * id_size as usize) + // field IDs
+ ((num_fields + 1) * offset_size as usize); // field offsets + data_size
+
+ let starting_offset = self.object_start_offset;
+
+ // Shift existing data to make room for the header
+ let buffer = parent_buffer.inner_mut();
+ buffer.splice(starting_offset..starting_offset, vec![0u8; header_size]);
Review Comment:
FYI, I think we can improve the performance of appending packed `u32` values to a `Vec<u8>`. The following code:
```rust
pub fn append_bytes_brute2(dest: &mut Vec<u8>, src: u32, nbytes: NumBytes) {
let n = dest.len() + nbytes as usize;
dest.extend(src.to_le_bytes());
dest.truncate(n);
}
```
... unconditionally adds all four bytes and then truncates the vector to the desired length. This works because (a) it's a single machine instruction to copy the four LE bytes of a `u32` to a memory location; (b) truncate drops the higher order bytes, when working with LE bytes; and (c) `truncate` is dirt cheap (conditional move that doesn't break processor pipelines the way a branch would).
Result: Code that should perform the same regardless of the number of bytes we encode the `u32` as, with only a single branch to check for vector capacity.
<details>
The above [compiles](https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=c4e3f95d39ad58148435d55ff7095a3a) to the following assembly code:
```asm
playground::append_packed_u32:
;; set up stack frame (not relevant in practice due to inlining)
...
movq (%rdi), %rcx ; dest capacity
movq 16(%rdi), %rbx ; dest len
subq %rbx, %rcx ; calculate available capacity
movq %rbx, %rax
cmpq $3, %rcx ; if insufficient capacity...
jbe .LBB2_1 ; ... then `reserve` more
.LBB2_2:
addq %rdx, %rbx ; add nbytes to len (truncate arg)
movq 8(%rdi), %rcx ; dest data pointer
movl %esi, (%rcx,%rax) ; append all four bytes of src to the vector
addq $4, %rax ; increase len by 4 (u32 size)
cmpq %rax, %rbx ; if new len is bigger than truncate arg...
cmovbq %rbx, %rax ; ... then truncate len
movq %rax, 16(%rdi) ; write back the updated dest len
;; tear down stack frame
...
retq
.LBB2_1:
;; call prologue
...
callq alloc::raw_vec::RawVecInner<A>::reserve::do_reserve_and_handle
;; call epilogue
...
jmp .LBB2_2
```
The one bummer is, when adding a `reserve` followed by a loop over a slice of source bytes:
```rust
pub fn append_packed_u32(dest: &mut Vec<u8>, src: &[u32], nbytes: usize) {
dest.reserve((src.len() + 1) * nbytes);
for val in src {
let n = dest.len() + nbytes;
dest.extend(val.to_le_bytes());
dest.truncate(n);
}
}
```
... the [compiler](https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=e0502909fe267e592ba37ede6e048281) isn't smart enough to eliminate the redundant capacity check inside the loop. Oh, well.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2218045675
##########
parquet-variant/src/builder.rs:
##########
@@ -1118,8 +1181,8 @@ impl<'a> ObjectBuilder<'a> {
/// Finalizes this object and appends it to its parent, which otherwise remains unmodified.
pub fn finish(mut self) -> Result<(), ArrowError> {
- let metadata_builder = self.parent_state.metadata_builder();
if self.validate_unique_fields && !self.duplicate_fields.is_empty() {
+ let metadata_builder = self.parent_state.metadata_builder();
Review Comment:
This wants to avoid the double mutable reference problem, but it's not a problem after the implementation has changed, I can revert this if needed.
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1078,29 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
+ object_start_offset: usize,
Review Comment:
Fixed
##########
parquet-variant/src/builder.rs:
##########
@@ -2357,8 +2673,8 @@ mod tests {
// Only the second attempt should appear in the final variant
let (metadata, value) = builder.finish();
let metadata = VariantMetadata::try_new(&metadata).unwrap();
- assert_eq!(metadata.len(), 1);
- assert_eq!(&metadata[0], "name"); // not rolled back
+ assert_eq!(metadata.len(), 1); // rolled back
+ assert_eq!(&metadata[0], "name");
Review Comment:
Fixed, my bad, this was unintentionally modified.
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1078,29 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
Review Comment:
Fixed
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
Review Comment:
IIUC, `metadata_builder.field_names.len()` returns the size of the underlying map, it may be bigger than the actual max `field_id`, changing to this here is that it can avoid one pass for the `field_ids` to calucalute the `max_id`.
But this change can make test more diffict(more difficult to calculate the header size) -- such as the failed case `from_json::test::test_json_to_variant_object_very_large` ([test code here](https://github.com/apache/arrow-rs/blob/82821e574df7e699c7a491da90c54429a5a439e9/parquet-variant-json/src/from_json.rs#L633)/[failed ci](https://github.com/apache/arrow-rs/actions/runs/16401976375/job/46342711866?pr=7935))
@alamb @viirya @scovich Maybe we can revert this to the original code(travel one pass from `filed_ids`) what do you think about this? thanks.
##########
parquet-variant/src/builder.rs:
##########
@@ -506,6 +506,7 @@ enum ParentState<'a> {
metadata_builder: &'a mut MetadataBuilder,
fields: &'a mut IndexMap<u32, usize>,
field_name: &'a str,
+ object_start_offset: usize,
Review Comment:
Fixed, `object_start_offset` wants to indicate that this is the offset of the current object start.
##########
parquet-variant/src/builder.rs:
##########
@@ -1028,18 +1078,29 @@ impl Drop for ListBuilder<'_> {
pub struct ObjectBuilder<'a> {
parent_state: ParentState<'a>,
fields: IndexMap<u32, usize>, // (field_id, offset)
- buffer: ValueBuffer,
+ /// the starting offset in the parent's buffer where this object starts
+ object_start_offset: usize,
+ /// the starting offset in the parent's metadata buffer where this object starts
+ /// used to truncate the written fields in `drop` if the current object has not been finished
+ object_meta_start_offset: usize,
Review Comment:
Fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2218119219
##########
parquet-variant/src/builder.rs:
##########
@@ -1134,39 +1197,86 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
- let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
+ // the length of the metadata's field names is a very cheap to compute the upper bound.
+ // it will almost always be a tight upper bound as well -- it would take a pretty
+ // carefully crafted object to use only the early field ids of a large dictionary.
+ let max_id = metadata_builder.field_names.len();
Review Comment:
IIUC, `metadata_builder.field_names.len()` returns the size of the underlying map, it may be bigger than the actual max `field_id`, changing to this here is that it can avoid one pass for the `field_ids` to calucalute the `max_id`.
But this change can make test more diffict(more difficult to calculate the header size) -- such as the failed case `from_json::test::test_json_to_variant_object_very_large` ([test code here](https://github.com/apache/arrow-rs/blob/82821e574df7e699c7a491da90c54429a5a439e9/parquet-variant-json/src/from_json.rs#L633)/[failed ci](https://github.com/apache/arrow-rs/actions/runs/16401976375/job/46342711866?pr=7935))
@alamb @viirya @scovich Maybe we can revert this to the original code(travel one pass from `filed_ids`) what do you think about this? thanks. -- added a separate commit which reverted this logic to see if any other tests failed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#issuecomment-3096721024
> @scovich Thank you very much for the detailed review and suggestion, I've addressed most of them (add comments for the rest), please take another look when you're free.
I'm excited to take a look ASAP, but I'll be on the road a lot this week. Please don't take my absenteeism as a lack of interest tho!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Avoid extra allocation in object builder [arrow-rs]
Posted by "klion26 (via GitHub)" <gi...@apache.org>.
klion26 commented on code in PR #7935:
URL: https://github.com/apache/arrow-rs/pull/7935#discussion_r2221326885
##########
parquet-variant/src/builder.rs:
##########
@@ -1275,38 +1330,80 @@ impl<'a> ObjectBuilder<'a> {
)));
}
- let data_size = self.buffer.offset();
- let num_fields = self.fields.len();
- let is_large = num_fields > u8::MAX as usize;
+ let metadata_builder = self.parent_state.metadata_builder();
self.fields.sort_by(|&field_a_id, _, &field_b_id, _| {
- let key_a = &metadata_builder.field_name(field_a_id as usize);
- let key_b = &metadata_builder.field_name(field_b_id as usize);
- key_a.cmp(key_b)
+ let field_a_name = metadata_builder.field_name(field_a_id as usize);
+ let field_b_name = metadata_builder.field_name(field_b_id as usize);
+ field_a_name.cmp(field_b_name)
});
-
let max_id = self.fields.iter().map(|(i, _)| *i).max().unwrap_or(0);
Review Comment:
change current logic to `let max_id = self.fields.len() - 1` will fail the `parquet_varient_json/from_json#test_json_to_variant_object_very_large` test, ~~I'm looking into it~~.
The tests failed because of `self.fields.len() - 1` may be different from `max(field ids)`
The difference comes from that there are objects inside objects. The schema looks like below(after some simplification)
```
{
"000": {
"240": [0,...,127],
"241": [0,...,127],
"495":[0,...,127],
}, <-- when the object finishes, there will be 256 field names in the metadatabuilder.field_names("240",.."495"), `self.fields.len()` equals to 256, the max_id will be 255
"001": {
"240": [0,...,127],
"241": [0,...,127],
"495":[0,...,127],
}, <-- when the object finishes, there will be 257 field names in the metadatabuilder.field_names("240",.."495", **"000"**), `self.fields.len()` equals to 256, the max_id will be 255
"002": {
"240": [0,...,127],
"241": [0,...,127],
"495":[0,...,127],
} <-- when the object finishes, there will be 258 field names in the metadatabuilder.field_names("240",.."495", **"000", "001"**, "002"),`self.fields.len()` equals to 256, the max_id will be 255
} <-- when the object finishes, there will be 258 field names in the metadatabuilder.field_names("240",.."495", **"000", "001", "002"**), `self.fields.len()` equals to 3 ("000", "001", "002"), the max_id will be 258
```
I'll dig into if there are any solutions we can optimize the max_id calculation logic.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org