Benchmark comparing two different ways to create a buffer builder

Demo.csproj

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net7.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
  </PropertyGroup>

  <ItemGroup>
    <PackageReference Include="BenchmarkDotNet" Version="0.13.5" />
  </ItemGroup>

</Project>

Program.cs

// 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 BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Engines;
using BenchmarkDotNet.Running;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

public static class BitUtility
{
    private static ReadOnlySpan<byte> PopcountTable => new byte[] {
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
        };

    private static ReadOnlySpan<byte> BitMask => new byte[] {
            1, 2, 4, 8, 16, 32, 64, 128
        };

    public static bool GetBit(byte data, int index) =>
        ((data >> index) & 1) != 0;

    public static bool GetBit(ReadOnlySpan<byte> data, int index) =>
        (data[index / 8] & BitMask[index % 8]) != 0;

    public static void ClearBit(Span<byte> data, int index)
    {
        data[index / 8] &= (byte)~BitMask[index % 8];
    }

    public static void SetBit(Span<byte> data, int index)
    {
        data[index / 8] |= BitMask[index % 8];
    }

    public static void SetBit(ref byte data, int index, bool value)
    {
        int mod = index % 8;
        data = value
            ? (byte)(data | BitMask[mod])
            : (byte)(data & ~BitMask[mod]);
    }

    public static void SetBit(Span<byte> data, int index, bool value)
    {
        int idx = index / 8;
        int mod = index % 8;
        data[idx] = value
            ? (byte)(data[idx] | BitMask[mod])
            : (byte)(data[idx] & ~BitMask[mod]);
    }

    public static void ToggleBit(Span<byte> data, int index)
    {
        data[index / 8] ^= BitMask[index % 8];
    }

    /// <summary>
    /// Counts the number of set bits in a span of bytes starting
    /// at a specific bit offset.
    /// </summary>
    /// <param name="data">Span to count bits</param>
    /// <param name="offset">Bit offset to start counting from</param>
    /// <returns>Count of set (one) bits</returns>
    public static int CountBits(ReadOnlySpan<byte> data, int offset) =>
        CountBits(data, offset, data.Length * 8 - offset);

    /// <summary>
    /// Counts the number of set bits in a span of bytes starting
    /// at a specific bit offset, and limiting to a certain number of bits
    /// in the span.
    /// </summary>
    /// <param name="data">Span to count bits.</param>
    /// <param name="offset">Bit offset to start counting from.</param>
    /// <param name="length">Maximum of bits in the span to consider.</param>
    /// <returns>Count of set (one) bits</returns>
    public static int CountBits(ReadOnlySpan<byte> data, int offset, int length)
    {
        int startByteIndex = offset / 8;
        int startBitOffset = offset % 8;
        int endByteIndex = (offset + length - 1) / 8;
        int endBitOffset = (offset + length - 1) % 8;
        if (startBitOffset < 0)
            return 0;

        int count = 0;
        if (startByteIndex == endByteIndex)
        {
            // Range starts and ends within the same byte.
            var slice = data.Slice(startByteIndex, 1);
            for (int i = startBitOffset; i <= endBitOffset; i++)
                count += GetBit(slice, i) ? 1 : 0;

            return count;
        }

        // If the starting index and ending index are not byte-aligned,
        // we'll need to count bits the slow way.  If they are
        // byte-aligned, and for all other bytes in the 'middle', we
        // can use a faster byte-aligned count.
        int fullByteStartIndex = startBitOffset == 0 ? startByteIndex : startByteIndex + 1;
        int fullByteEndIndex = endBitOffset == 7 ? endByteIndex : endByteIndex - 1;

        if (startBitOffset != 0)
        {
            var slice = data.Slice(startByteIndex, 1);
            for (int i = startBitOffset; i <= 7; i++)
                count += GetBit(slice, i) ? 1 : 0;
        }

        if (fullByteEndIndex >= fullByteStartIndex)
        {
            var slice = data.Slice(fullByteStartIndex, fullByteEndIndex - fullByteStartIndex + 1);
            count += CountBits(slice);
        }

        if (endBitOffset != 7)
        {
            var slice = data.Slice(endByteIndex, 1);
            for (int i = 0; i <= endBitOffset; i++)
                count += GetBit(slice, i) ? 1 : 0;
        }

        return count;
    }

    /// <summary>
    /// Counts the number of set bits in a span of bytes.
    /// </summary>
    /// <param name="data">Span to count bits</param>
    /// <returns>Count of set (one) bits.</returns>
    public static int CountBits(ReadOnlySpan<byte> data)
    {
        int count = 0;
        foreach (byte t in data)
            count += PopcountTable[t];
        return count;
    }

    /// <summary>
    /// Rounds an integer to the nearest multiple of 64.
    /// </summary>
    /// <param name="n">Integer to round.</param>
    /// <returns>Integer rounded to the nearest multiple of 64.</returns>
    public static long RoundUpToMultipleOf64(long n) =>
        RoundUpToMultiplePowerOfTwo(n, 64);

    /// <summary>
    /// Rounds an integer to the nearest multiple of 8.
    /// </summary>
    /// <param name="n">Integer to round.</param>
    /// <returns>Integer rounded to the nearest multiple of 8.</returns>
    public static long RoundUpToMultipleOf8(long n) =>
        RoundUpToMultiplePowerOfTwo(n, 8);

    /// <summary>
    /// Rounds an integer up to the nearest multiple of factor, where
    /// factor must be a power of two.
    ///
    /// This function does not throw when the factor is not a power of two.
    /// </summary>
    /// <param name="n">Integer to round up.</param>
    /// <param name="factor">Power of two factor to round up to.</param>
    /// <returns>Integer rounded up to the nearest power of two.</returns>
    public static long RoundUpToMultiplePowerOfTwo(long n, int factor)
    {
        // Assert that factor is a power of two.
        Debug.Assert(factor > 0 && (factor & (factor - 1)) == 0);
        return (n + (factor - 1)) & ~(factor - 1);
    }

    internal static bool IsMultipleOf8(long n) => n % 8 == 0;

    /// <summary>
    /// Calculates the number of bytes required to store n bits.
    /// </summary>
    /// <param name="n">number of bits</param>
    /// <returns>number of bytes</returns>
    public static int ByteCount(int n)
    {
        Debug.Assert(n >= 0);
        return n / 8 + (n % 8 != 0 ? 1 : 0); // ceil(n / 8)
    }

    internal static int ReadInt32(ReadOnlyMemory<byte> value)
    {
        Debug.Assert(value.Length >= sizeof(int));

        return Unsafe.ReadUnaligned<int>(ref MemoryMarshal.GetReference(value.Span));
    }

    // Bytes
    public static byte ToByte(ref byte data, ReadOnlySpan<bool> bits)
    {
        for (int i = 0; i < Math.Min(8, bits.Length); i++)
        {
            SetBit(ref data, i, bits[i]);
        }
        return data;
    }

    public static void ToBytes(Span<byte> bytes, ReadOnlySpan<bool> bits)
    {
        for (int i = 0; i < bytes.Length; i++)
        {
            ToByte(ref bytes[i], bits.Slice(i * 8));
        }
    }

    // Bits
    public static void ToBits(Span<bool> bools, byte value)
    {
        for (int i = 0; i < 8; i++)
        {
            bools[i] = GetBit(value, i);
        }
    }

    public static bool[] ToBits(byte value)
    {
        bool[] boolArray = new bool[8]; // initialize bool array with correct length

        for (int i = 0; i < 8; i++)
        {
            boolArray[i] = GetBit(value, i);
        }

        return boolArray;
    }

    public static void ToBits(Span<bool> bits, ReadOnlySpan<byte> bytes)
    {
        for (int i = 0; i < bytes.Length; i++)
        {
            ToBits(bits.Slice(i * 8, 8), bytes[i]);
        }
    }

    public static Span<bool> ToBits(ReadOnlySpan<byte> bytes)
    {
        Span<bool> bits = new bool[bytes.Length * 8].AsSpan();

        ToBits(bits, bytes);

        return bits;
    }

    internal static int NextPowerOfTwo(int n)
    {
        // 16 for int32
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }
}


public class BufferBuilder
{
    public class BitBuffer
    {
        private readonly bool[] _bits;

        public int Length { get; private set; }
        public int AvailableLength => Capacity - Length;

        public int Capacity;

        public bool IsFull => Length == Capacity;
        public byte ToByte(ref byte data) => BitUtility.ToByte(ref data, _bits);

        public BitBuffer(int capacity = 8)
        {
            Capacity = capacity;
            _bits = new bool[capacity];
            Length = 0;
        }

        public void Append(bool bit) => _bits[Length++] = bit;
        public void Fill(ReadOnlySpan<bool> bits)
        {
            bits.CopyTo(_bits.AsSpan().Slice(Length, bits.Length));
            Length += bits.Length;
        }

        public void Reset()
        {
            for (int i = 0; i < _bits.Length; i++)
            {
                _bits[i] = false;
            }
            Length = 0;
        }
    }

    private const int DefaultCapacity = 64;
    public int ByteLength { get; private set; }

    public Memory<byte> Memory { get; private set; }
    public BitBuffer BitOverhead { get; }

    /// <summary>
    /// Creates an instance of the <see cref="BufferBuilder"/> class.
    /// </summary>
    /// <param name="valueBitSize">Number of bits of one value item.</param>
    /// <param name="capacity">Number of items of initial capacity to reserve.</param>
    public BufferBuilder(int capacity = DefaultCapacity)
    {
        Memory = new byte[capacity];
        BitOverhead = new BitBuffer();

        ByteLength = 0;
    }

    private void CommitBitBuffer(bool force = false)
    {
        if (BitOverhead.IsFull || force)
        {
            EnsureAdditionalBytes(1);
            BitOverhead.ToByte(ref Memory.Span[ByteLength]);
            BitOverhead.Reset();
            ByteLength++;
        }
    }

    public BufferBuilder AppendBit(bool bit)
    {
        BitOverhead.Append(bit);
        CommitBitBuffer();
        return this;
    }

    public BufferBuilder AppendBits(ReadOnlySpan<bool> bits)
    {
        if (BitOverhead.Length > 0)
        {
            int available = BitOverhead.AvailableLength;

            if (bits.Length > available)
            {
                // Fill byte buffer
                BitOverhead.Fill(bits.Slice(0, available));

                // Commit to memory and reset
                CommitBitBuffer();

                bits = bits.Slice(available);
            }
            else
            {
                // Fill byte buffer
                BitOverhead.Fill(bits);

                bits = ReadOnlySpan<bool>.Empty;
            }
        }

        if (bits.Length > 0)
        {
            int byteEnd = bits.Length / 8;
            int bitEnd = byteEnd * 8;

            if (byteEnd > 0)
            {
                // Ensure byte length
                EnsureAdditionalBytes(byteEnd);

                // Raw Span copy to memory
                BitUtility.ToBytes(Memory.Span.Slice(ByteLength, byteEnd), bits.Slice(0, bitEnd));

                ByteLength += byteEnd;

                bits = bits.Slice(bitEnd);
            }

            if (bits.Length > 0)
            {
                // Fill byte buffer with last unfilled
                BitOverhead.Fill(bits);
            }
        }

        return this;
    }

    public BufferBuilder AppendBits(bool value, int count)
    {
        Span<bool> span = new bool[count];

        // default bool are already false
        if (value)
            for (int i = 0; i < count; i++)
                span[i] = value;

        return AppendBits(span);
    }

    public BufferBuilder AppendByte(byte byteValue)
    {
        if (BitOverhead.Length > 0)
        {
            // Fill current bit buffer
            int available = BitOverhead.AvailableLength;

            // Convert byte to bit array
            Span<bool> bits = BitUtility.ToBits(byteValue).AsSpan();

            // Fill byte buffer
            BitOverhead.Fill(bits.Slice(0, available));

            // Commit to memory and reset
            CommitBitBuffer();

            // Fill new bit buffer
            BitOverhead.Fill(bits.Slice(available));
        }
        else
        {
            EnsureAdditionalBytes(1);
            // Raw add to memory
            Memory.Span[ByteLength] = byteValue;
            ByteLength++;
        }

        return this;
    }

    public BufferBuilder AppendBytes(ReadOnlySpan<byte> bytes)
    {
        if (BitOverhead.Length == 0)
        {
            EnsureAdditionalBytes(bytes.Length);
            // Raw Span copy to memory
            bytes.CopyTo(Memory.Span.Slice(ByteLength, bytes.Length));
            ByteLength += bytes.Length;
        }
        else
        {
            // Convert Bytes to Bits streamed in batchsize = 64
            int offset = 0;
            while (offset < bytes.Length)
            {
                int remainingBytes = bytes.Length - offset;
                int bufferLength = Math.Min(128, remainingBytes);

                // Bits span
                Span<bool> buffer = new bool[bufferLength * 8];

                // Fill bits
                BitUtility.ToBits(buffer, bytes.Slice(offset, bufferLength));

                // Append batch bits
                AppendBits(buffer);
                offset += bufferLength;
            }
        }

        return this;
    }

    internal BufferBuilder ReserveBytes(int numBytes)
    {
        EnsureAdditionalBytes(numBytes);
        return this;
    }

    internal BufferBuilder ResizeBytes(int numBytes)
    {
        EnsureBytes(numBytes);
        ByteLength = numBytes;
        return this;
    }

    public BufferBuilder Clear()
    {
        Memory.Span.Fill(default);
        ByteLength = 0;
        return this;
    }

    private void EnsureAdditionalBytes(int numBytes) => EnsureBytes(checked(ByteLength + numBytes));

    internal void EnsureBytes(int numBytes)
    {
        if (numBytes > Memory.Length)
        {
            int twice = checked(Memory.Length * 2);

            Reallocate(twice < numBytes ? BitUtility.NextPowerOfTwo(numBytes) : twice);
        }
    }

    private void Reallocate(int numBytes)
    {
        var memory = new Memory<byte>(new byte[numBytes]);
        Memory.CopyTo(memory);

        Memory = memory;
    }
}

public class NoOverheadBufferBuilder
{
    private const int DefaultCapacity = 64;
    public int ByteLength { get; private set; }
    public int BitOffset { get; private set; }

    public Memory<byte> Memory { get; private set; }

    /// <summary>
    /// Creates an instance of the <see cref="BufferBuilder"/> class.
    /// </summary>
    /// <param name="valueBitSize">Number of bits of one value item.</param>
    /// <param name="capacity">Number of items of initial capacity to reserve.</param>
    public NoOverheadBufferBuilder(int capacity = DefaultCapacity)
    {
        Memory = new byte[capacity];
        ByteLength = 0;
        BitOffset = 0;
    }

    public void AppendBit(bool bit)
    {
        BitUtility.SetBit(ref Memory.Span[ByteLength], BitOffset, bit);
        BitOffset++;
        if (BitOffset == 8)
        {
            BitOffset = 0;
            ByteLength++;
            EnsureBytes(ByteLength);
        }
    }

    public void AppendBits(bool value, int count)
    {
        int remainderBits = Math.Min(count, 8 - BitOffset);
        int wholeBytes = (count - remainderBits) / 8;
        int trailingBits = count - remainderBits - (wholeBytes * 8);
        int newBytes = (trailingBits > 0) ? wholeBytes + 1 : wholeBytes;

        EnsureAdditionalBytes(newBytes);

        var span = Memory.Span;
        for (int i = 0; i < remainderBits; i++)
        {
            BitUtility.SetBit(ref span[ByteLength], BitOffset, value);
            BitOffset++;
        }
        if (BitOffset == 8)
        {
            BitOffset = 0;
            ByteLength++;
        }

        if (wholeBytes > 0)
        {
            var fill = (byte)(value ? 0xFF : 0x00);
            span.Slice(ByteLength, wholeBytes).Fill(fill);
        }
        ByteLength += wholeBytes;

        for (int i = 0; i < trailingBits; i++)
        {
            BitUtility.SetBit(ref span[ByteLength], BitOffset, value);
            BitOffset++;
        }
    }

    public void Clear()
    {
        Memory.Span.Fill(default);
        ByteLength = 0;
        BitOffset = 0;
    }

    private void EnsureAdditionalBytes(int numBytes) => EnsureBytes(checked(ByteLength + numBytes));

    internal void EnsureBytes(int numBytes)
    {
        if (numBytes > Memory.Length)
        {
            int twice = checked(Memory.Length * 2);

            Reallocate(twice < numBytes ? BitUtility.NextPowerOfTwo(numBytes) : twice);
        }
    }

    private void Reallocate(int numBytes)
    {
        var memory = new Memory<byte>(new byte[numBytes]);
        Memory.CopyTo(memory);

        Memory = memory;
    }
}

public class Benchmarks
{
    private BufferBuilder builder = new BufferBuilder();
    private NoOverheadBufferBuilder noOverheadBuilder = new NoOverheadBufferBuilder();

    [Params(1, 100, 10000, 100000)]
    public int NumBits { get; set; }

    [Benchmark]
    public void AppendFalse()
    {
        builder.AppendBits(false, NumBits);
        builder.Clear();
    }

    [Benchmark]
    public void AppendTrue()
    {
        builder.AppendBits(true, NumBits);
        builder.Clear();
    }

    [Benchmark]
    public void AppendFalseNoOverhead()
    {
        noOverheadBuilder.AppendBits(false, NumBits);
        noOverheadBuilder.Clear();
    }

    [Benchmark]
    public void AppendTrueNoOverhead()
    {
        noOverheadBuilder.AppendBits(true, NumBits);
        noOverheadBuilder.Clear();
    }
}


public class Program
{
    public static void Main()
    {
        // BenchmarkRunner.Run<Benchmarks>(new DebugInProcessConfig());
        BenchmarkRunner.Run<Benchmarks>();
    }
}