CurtHagenlocher commented on code in PR #504:
URL: https://github.com/apache/arrow-dotnet/pull/504#discussion_r4580802220
##########
src/Apache.Arrow/Arrays/PrimitiveArrayBuilder.cs:
##########
@@ -98,42 +120,94 @@ public TBuilder Clear()
protected abstract TTo ConvertTo(TFrom value);
}
- public abstract class PrimitiveArrayBuilder<T, TArray, TBuilder> :
IArrowArrayBuilder<T, TArray, TBuilder>
+ public abstract class PrimitiveArrayBuilder<T, TArray, TBuilder> :
IArrowArrayBuilder<T, TArray, TBuilder>, IDisposable
where T : struct
where TArray : IArrowArray
where TBuilder : class, IArrowArrayBuilder<TArray>
{
+ // Created when the first null is appended. Until then every element
is valid, which
+ // is what an empty validity buffer means, so arrays without nulls
never allocate one.
+ private ArrowBuffer.BitmapBuilder _validity;
+
+ // Kept so that a bitmap created later uses the same allocator as the
values. May be
+ // null, which means managed working memory copied into the default
allocator on Build.
+ private readonly MemoryAllocator _allocator;
+
protected TBuilder Instance => this as TBuilder;
protected ArrowBuffer.Builder<T> ValueBuffer { get; }
- protected ArrowBuffer.BitmapBuilder ValidityBuffer { get; }
+
+ /// <summary>
+ /// The validity bitmap. Reading this creates the bitmap if no null
has been appended
+ /// yet, marking every element so far as valid.
+ /// </summary>
+ protected ArrowBuffer.BitmapBuilder ValidityBuffer => _validity ??=
CreateValidityBuffer();
public int Length => ValueBuffer.Length;
- protected int NullCount => ValidityBuffer.UnsetBitCount;
+ protected int NullCount => _validity?.UnsetBitCount ?? 0;
+
+ // The initial capacity builders have always had, matching
ArrowBuffer.Builder<T>.
+ private const int DefaultCapacity = 8;
+ // The smallest bitmap to create, in bits: BitmapBuilder's own
default. Sizing the bitmap
+ // only to the value capacity would start it at a single byte and make
it grow repeatedly.
+ private const int MinimumValidityCapacity = 64;
+
+ /// <summary>
+ /// Creates a builder with room for a few values, which grows as
values are appended.
+ /// </summary>
public PrimitiveArrayBuilder()
+ : this(DefaultCapacity, null)
{
- ValueBuffer = new ArrowBuffer.Builder<T>();
- ValidityBuffer = new ArrowBuffer.BitmapBuilder();
+ }
+
+ /// <summary>
+ /// Creates a builder with room for <paramref name="capacity"/>
values. A builder given
+ /// its final length allocates once, and that memory becomes the built
array's memory.
+ /// </summary>
+ /// <param name="capacity">Number of values to allocate room
for.</param>
+ /// <param name="allocator">
+ /// Allocator for the builder's working memory, which usually becomes
the built array's
+ /// memory. When <c>null</c>, the builder works in managed memory and
copies
+ /// what it builds into <see cref="MemoryAllocator.Default"/>, as
builders always have.
+ /// </param>
+ protected PrimitiveArrayBuilder(int capacity, MemoryAllocator
allocator = null)
+ {
+ if (capacity < 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(capacity));
+ }
+
+ _allocator = allocator;
+ ValueBuffer = new ArrowBuffer.Builder<T>(capacity, _allocator);
}
public TBuilder Resize(int length)
{
+ if (length > ValueBuffer.Length)
+ {
+ // Elements added by growing are null, so the bitmap is needed
to record that.
+ ValidityBuffer.Resize(length);
Review Comment:
Good catch, fixed in 35cd570. A growing `BitmapBuilder.Resize` now
explicitly unsets the bits it adds instead of relying on the allocator to zero
them, which also covers bits left over from an earlier truncation. Testing with
`GarbageMemoryAllocator` turned up the same assumption in `Clear()` after a
build and in the padding of copied buffers; both now zero explicitly. Covered
by `BuilderEdgeCaseTests`.
##########
src/Apache.Arrow/ArrowBuffer.Builder.cs:
##########
@@ -242,22 +324,30 @@ private void EnsureCapacity(int requiredCapacity)
// TODO: specifiable growth strategy
// Double the length of the in-memory array, or use the
byte count of the capacity, whichever is
// greater.
- int capacity = Math.Max(requiredCapacity * _size,
Memory.Length * 2);
- Reallocate(capacity);
+ int capacity = Math.Max(checked(requiredCapacity * Size),
_buffer.Capacity * 2);
+
+ // Grow through the allocator so that the builder's
working memory is
+ // visible to it, and so that allocators able to grow in
place can do so.
+ _buffer.Grow(capacity);
Review Comment:
Agreed, fixed in 35cd570 for both
`ArrowBuffer.Builder<T>.Append(ReadOnlySpan<T>)` and
`BitmapBuilder.Append(ReadOnlySpan<byte>, int)`. When an append has to grow and
the source overlaps the builder's own memory, the source is copied first. The
overlap check only runs when growth is needed. Tested with a poisoning
`PooledManagedAllocator`.
##########
src/Apache.Arrow/Memory/BuilderMemory.cs:
##########
@@ -0,0 +1,267 @@
+// Licensed to the Apache Software Foundation (ASF) under one or more
+// contributor license agreements. See the NOTICE file distributed with
+// this work for additional information regarding copyright ownership.
+// The ASF licenses this file to You under the Apache License, Version 2.0
+// (the "License"); you may not use this file except in compliance with
+// the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+using System;
+using System.Buffers;
+
+namespace Apache.Arrow.Memory
+{
+ /// <summary>
+ /// The working memory of a buffer builder.
+ /// </summary>
+ /// <remarks>
+ /// <para>
+ /// Working memory grows in a <em>temporary</em> allocator and the built
buffer belongs to a
+ /// <em>long-term</em> one. When the two are the same allocator, the
working memory can be
+ /// handed to the built buffer instead of being copied; otherwise building
copies it.
+ /// </para>
+ /// <para>
+ /// A builder given no allocator uses managed memory as its temporary
allocator and
+ /// <see cref="MemoryAllocator.Default"/> as its long-term one, exactly
reproducing how
+ /// builders have always behaved: growth never touches native memory, and
building makes a
+ /// single native allocation of the exact size. Passing an allocator opts
into the hand-over.
+ /// </para>
+ /// <para>
+ /// After a hand-over the builder no longer owns writable memory. It keeps
a retained
+ /// reference to the built buffer so that its contents stay readable, and
copies them into
+ /// fresh working memory the first time the builder is written to again.
Code that builds
+ /// once and discards the builder therefore allocates once; code that
keeps appending after
+ /// a build pays one copy, which is what every build cost before.
+ /// </para>
+ /// <para>
+ /// When it can hand over, working memory is always a multiple of <see
cref="Padding"/>
+ /// bytes, so that a builder created with the right capacity never has to
grow to pad its
+ /// result.
+ /// </para>
+ /// </remarks>
+ internal sealed class BuilderMemory : IDisposable
+ {
+ internal const int Padding = 64;
+
+ /// <summary>
+ /// Hand over only when at most this fraction of the working memory
would be unused
+ /// (1/2). Doubling growth means this almost always holds; it rules
out handing a large
+ /// reservation to a small array, which would hold the slack for the
array's lifetime.
+ /// </summary>
+ private const int MaxSlackDivisor = 2;
+
+ private readonly MemoryAllocator _temporary;
+ private readonly MemoryAllocator _longTerm;
+ private readonly bool _canHandOver;
+
+ // Exactly one of these is in use: _owner/_memory while the builder
owns its working
+ // memory, _shared after that memory has been handed to a built
buffer. Both are empty
+ // after disposal.
+ private IMemoryOwner<byte> _owner;
+ private Memory<byte> _memory;
+ private ArrowBuffer _shared;
+ private bool _isShared;
+
+ /// <param name="allocator">
+ /// The allocator for both working memory and built buffers, or
<c>null</c> for managed
+ /// working memory copied into <see cref="MemoryAllocator.Default"/>
when built.
+ /// </param>
+ /// <param name="capacityBytes">Initial capacity in bytes.</param>
+ public BuilderMemory(MemoryAllocator allocator, int capacityBytes)
+ : this(allocator ?? ManagedMemoryAllocator.Instance, allocator ??
MemoryAllocator.Default.Value, capacityBytes)
+ {
+ }
+
+ private BuilderMemory(MemoryAllocator temporary, MemoryAllocator
longTerm, int capacityBytes)
+ {
+ if (capacityBytes < 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(capacityBytes));
+ }
+
+ _temporary = temporary;
+ _longTerm = longTerm;
+ _canHandOver = ReferenceEquals(temporary, longTerm);
+ _owner = _temporary.Allocate(RoundUp(capacityBytes));
+ _memory = _owner.Memory;
+ }
+
+ /// <summary>
+ /// Whether built buffers can take over the working memory. When
false, the builder
+ /// behaves exactly as builders always have.
+ /// </summary>
+ public bool CanHandOver => _canHandOver;
+
+ /// <summary>
+ /// Size of the working memory in bytes. Reading this never copies.
+ /// </summary>
+ public int Capacity => _isShared ? _shared.Length : _memory.Length;
+
+ /// <summary>
+ /// The writable working memory. If it has been handed to a built
buffer, the contents
+ /// are first copied into memory the builder owns, so writes never
reach that buffer.
+ /// </summary>
+ public Memory<byte> Memory
+ {
+ get
+ {
+ if (_isShared)
+ {
+ Detach(_shared.Length);
+ }
+
+ return _memory;
+ }
+ }
+
+ /// <summary>
+ /// Grows the working memory to at least <paramref
name="capacityBytes"/>, preserving
+ /// its contents and zeroing the added region.
+ /// </summary>
+ public void Grow(int capacityBytes)
+ {
+ int rounded = RoundUp(capacityBytes);
+ if (rounded <= Capacity)
+ {
+ return;
+ }
+
+ if (_isShared)
+ {
+ Detach(rounded);
+ return;
+ }
+
+ ThrowIfDisposed();
+ _owner = _temporary.Resize(_owner, rounded);
+ _memory = _owner.Memory;
+ }
+
+ /// <summary>
+ /// Zeroes the working memory, keeping its capacity. Discards rather
than copies memory
+ /// that was handed to a built buffer, so clearing a builder after a
build is cheap.
+ /// </summary>
+ public void Reset()
+ {
+ if (_isShared)
+ {
+ int capacity = _shared.Length;
+ ReleaseShared();
+ _owner = _temporary.Allocate(capacity);
+ _memory = _owner.Memory;
+ return;
+ }
+
+ _memory.Span.Clear();
+ }
+
+ /// <summary>
+ /// Builds a buffer holding the first <paramref name="usedBytes"/>
bytes, zero-padded to
+ /// a multiple of <paramref name="byteSize"/>.
+ /// </summary>
+ /// <param name="target">
+ /// Allocator that should own the result; <c>null</c> means this
builder's long-term
+ /// allocator. The working memory is handed over only when that is
also the temporary
+ /// allocator; otherwise the data is copied.
+ /// </param>
+ public ArrowBuffer Build(int usedBytes, int byteSize, MemoryAllocator
target)
+ {
+ int padded =
checked((int)BitUtility.RoundUpToMultiplePowerOfTwo(usedBytes, byteSize));
+ MemoryAllocator destination = target ?? _longTerm;
+ bool handOver = _canHandOver && ReferenceEquals(destination,
_temporary);
+
+ if (_isShared)
+ {
+ // Built again without being written to: share the same memory.
+ if (handOver && padded == _shared.Length)
+ {
+ return _shared.Retain();
Review Comment:
Yes, fixed in 35cd570. `BuilderMemory` now records how many bytes the shared
buffer actually holds, and only reuses it when a later build would hold exactly
the same bytes. After a shrinking `Resize`, the build copies into a new,
zero-padded buffer and leaves the earlier buffer untouched. Covered by
`RebuildingAfterShrinkingDoesNotExposeRemovedValues`.
##########
src/Apache.Arrow/Memory/BuilderMemory.cs:
##########
@@ -0,0 +1,267 @@
+// Licensed to the Apache Software Foundation (ASF) under one or more
+// contributor license agreements. See the NOTICE file distributed with
+// this work for additional information regarding copyright ownership.
+// The ASF licenses this file to You under the Apache License, Version 2.0
+// (the "License"); you may not use this file except in compliance with
+// the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+using System;
+using System.Buffers;
+
+namespace Apache.Arrow.Memory
+{
+ /// <summary>
+ /// The working memory of a buffer builder.
+ /// </summary>
+ /// <remarks>
+ /// <para>
+ /// Working memory grows in a <em>temporary</em> allocator and the built
buffer belongs to a
+ /// <em>long-term</em> one. When the two are the same allocator, the
working memory can be
+ /// handed to the built buffer instead of being copied; otherwise building
copies it.
+ /// </para>
+ /// <para>
+ /// A builder given no allocator uses managed memory as its temporary
allocator and
+ /// <see cref="MemoryAllocator.Default"/> as its long-term one, exactly
reproducing how
+ /// builders have always behaved: growth never touches native memory, and
building makes a
+ /// single native allocation of the exact size. Passing an allocator opts
into the hand-over.
+ /// </para>
+ /// <para>
+ /// After a hand-over the builder no longer owns writable memory. It keeps
a retained
+ /// reference to the built buffer so that its contents stay readable, and
copies them into
+ /// fresh working memory the first time the builder is written to again.
Code that builds
+ /// once and discards the builder therefore allocates once; code that
keeps appending after
+ /// a build pays one copy, which is what every build cost before.
+ /// </para>
+ /// <para>
+ /// When it can hand over, working memory is always a multiple of <see
cref="Padding"/>
+ /// bytes, so that a builder created with the right capacity never has to
grow to pad its
+ /// result.
+ /// </para>
+ /// </remarks>
+ internal sealed class BuilderMemory : IDisposable
+ {
+ internal const int Padding = 64;
+
+ /// <summary>
+ /// Hand over only when at most this fraction of the working memory
would be unused
+ /// (1/2). Doubling growth means this almost always holds; it rules
out handing a large
+ /// reservation to a small array, which would hold the slack for the
array's lifetime.
+ /// </summary>
+ private const int MaxSlackDivisor = 2;
+
+ private readonly MemoryAllocator _temporary;
+ private readonly MemoryAllocator _longTerm;
+ private readonly bool _canHandOver;
+
+ // Exactly one of these is in use: _owner/_memory while the builder
owns its working
+ // memory, _shared after that memory has been handed to a built
buffer. Both are empty
+ // after disposal.
+ private IMemoryOwner<byte> _owner;
+ private Memory<byte> _memory;
+ private ArrowBuffer _shared;
+ private bool _isShared;
+
+ /// <param name="allocator">
+ /// The allocator for both working memory and built buffers, or
<c>null</c> for managed
+ /// working memory copied into <see cref="MemoryAllocator.Default"/>
when built.
+ /// </param>
+ /// <param name="capacityBytes">Initial capacity in bytes.</param>
+ public BuilderMemory(MemoryAllocator allocator, int capacityBytes)
+ : this(allocator ?? ManagedMemoryAllocator.Instance, allocator ??
MemoryAllocator.Default.Value, capacityBytes)
+ {
+ }
+
+ private BuilderMemory(MemoryAllocator temporary, MemoryAllocator
longTerm, int capacityBytes)
+ {
+ if (capacityBytes < 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(capacityBytes));
+ }
+
+ _temporary = temporary;
+ _longTerm = longTerm;
+ _canHandOver = ReferenceEquals(temporary, longTerm);
+ _owner = _temporary.Allocate(RoundUp(capacityBytes));
+ _memory = _owner.Memory;
+ }
+
+ /// <summary>
+ /// Whether built buffers can take over the working memory. When
false, the builder
+ /// behaves exactly as builders always have.
+ /// </summary>
+ public bool CanHandOver => _canHandOver;
+
+ /// <summary>
+ /// Size of the working memory in bytes. Reading this never copies.
+ /// </summary>
+ public int Capacity => _isShared ? _shared.Length : _memory.Length;
+
+ /// <summary>
+ /// The writable working memory. If it has been handed to a built
buffer, the contents
+ /// are first copied into memory the builder owns, so writes never
reach that buffer.
+ /// </summary>
+ public Memory<byte> Memory
+ {
+ get
+ {
+ if (_isShared)
+ {
+ Detach(_shared.Length);
+ }
+
+ return _memory;
+ }
+ }
+
+ /// <summary>
+ /// Grows the working memory to at least <paramref
name="capacityBytes"/>, preserving
+ /// its contents and zeroing the added region.
+ /// </summary>
+ public void Grow(int capacityBytes)
+ {
+ int rounded = RoundUp(capacityBytes);
+ if (rounded <= Capacity)
+ {
+ return;
+ }
+
+ if (_isShared)
+ {
+ Detach(rounded);
+ return;
+ }
+
+ ThrowIfDisposed();
+ _owner = _temporary.Resize(_owner, rounded);
+ _memory = _owner.Memory;
+ }
+
+ /// <summary>
+ /// Zeroes the working memory, keeping its capacity. Discards rather
than copies memory
+ /// that was handed to a built buffer, so clearing a builder after a
build is cheap.
+ /// </summary>
+ public void Reset()
+ {
+ if (_isShared)
+ {
+ int capacity = _shared.Length;
+ ReleaseShared();
+ _owner = _temporary.Allocate(capacity);
+ _memory = _owner.Memory;
+ return;
+ }
+
+ _memory.Span.Clear();
+ }
+
+ /// <summary>
+ /// Builds a buffer holding the first <paramref name="usedBytes"/>
bytes, zero-padded to
+ /// a multiple of <paramref name="byteSize"/>.
+ /// </summary>
+ /// <param name="target">
+ /// Allocator that should own the result; <c>null</c> means this
builder's long-term
+ /// allocator. The working memory is handed over only when that is
also the temporary
+ /// allocator; otherwise the data is copied.
+ /// </param>
+ public ArrowBuffer Build(int usedBytes, int byteSize, MemoryAllocator
target)
+ {
+ int padded =
checked((int)BitUtility.RoundUpToMultiplePowerOfTwo(usedBytes, byteSize));
+ MemoryAllocator destination = target ?? _longTerm;
+ bool handOver = _canHandOver && ReferenceEquals(destination,
_temporary);
+
+ if (_isShared)
+ {
+ // Built again without being written to: share the same memory.
+ if (handOver && padded == _shared.Length)
+ {
+ return _shared.Retain();
+ }
+
+ return Copy(_shared.Span, usedBytes, padded, destination);
+ }
+
+ ThrowIfDisposed();
+
+ if (!handOver || padded == 0 || padded > _memory.Length ||
+ _memory.Length - padded > _memory.Length / MaxSlackDivisor)
+ {
+ return Copy(_memory.Span, usedBytes, padded, destination);
+ }
+
+ // The bytes between the data and the padding boundary may hold
values left behind
+ // by a Resize or a Set, which the copying path would have left as
zero.
+ _memory.Span.Slice(usedBytes, padded - usedBytes).Clear();
+
+ IMemoryOwner<byte> owner = padded == _memory.Length
+ ? _owner
+ : new SlicedMemoryOwner(_owner, padded);
+
+ ArrowBuffer result = new ArrowBuffer(owner, _temporary.Lifetime);
+ _shared = result.Retain();
+ _isShared = true;
+ _owner = null;
+ _memory = Memory<byte>.Empty;
+
+ return result;
+ }
+
+ public void Dispose()
+ {
+ if (_isShared)
+ {
+ ReleaseShared();
+ return;
+ }
+
+ IMemoryOwner<byte> owner = _owner;
+ _owner = null;
+ _memory = Memory<byte>.Empty;
+ owner?.Dispose();
+ }
+
+ private void Detach(int capacityBytes)
+ {
+ IMemoryOwner<byte> owner = _temporary.Allocate(capacityBytes);
+ _shared.Span.CopyTo(owner.Memory.Span);
+ ReleaseShared();
+ _owner = owner;
+ _memory = owner.Memory;
+ }
+
+ private void ReleaseShared()
+ {
+ ArrowBuffer shared = _shared;
+ _shared = default;
+ _isShared = false;
+ shared.Dispose();
+ }
+
+ private static ArrowBuffer Copy(ReadOnlySpan<byte> source, int
usedBytes, int padded, MemoryAllocator allocator)
+ {
+ IMemoryOwner<byte> owner = allocator.Allocate(padded);
+ source.Slice(0, usedBytes).CopyTo(owner.Memory.Span);
+ return new ArrowBuffer(owner, allocator.Lifetime);
+ }
Review Comment:
Right, this is the same pattern as the writer. Fixed in 35cd570: both
copying paths in `BuilderMemory.Build` now call `GC.KeepAlive(this)` after the
copy, so the working memory can't be finalized while it's being read. As with
the writer fix, Debug builds extend lifetimes, so there's no unit test for this.
##########
src/Apache.Arrow/Arrays/ArrayDataConcatenator.cs:
##########
@@ -611,9 +611,9 @@ public void Visit(RunEndEncodedType type)
switch (runEndsTypeId)
{
- case ArrowTypeId.Int16: int16Builder = new
ArrowBuffer.Builder<short>(); break;
- case ArrowTypeId.Int32: int32Builder = new
ArrowBuffer.Builder<int>(); break;
- case ArrowTypeId.Int64: int64Builder = new
ArrowBuffer.Builder<long>(); break;
+ case ArrowTypeId.Int16: int16Builder = new
ArrowBuffer.Builder<short>(0, _allocator); break;
+ case ArrowTypeId.Int32: int32Builder = new
ArrowBuffer.Builder<int>(0, _allocator); break;
+ case ArrowTypeId.Int64: int64Builder = new
ArrowBuffer.Builder<long>(0, _allocator); break;
Review Comment:
Fixed in 35cd570. The run-end builders are now `using` declarations, so
they're released even if concatenation throws. A builder with no capacity
allocates nothing, so all three are declared and only the one for the run-ends
type is used. Covered by `FailedRunEndConcatenationReleasesItsWorkingMemory`,
which overflows Int16 run ends and checks that nothing is left outstanding.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]