Repository: tetratelabs/wazero
Pull request #1467 (2023-05-15 06:47:45)

compiler: compress code offsets
A major source of memory utilization came from the two `[]uint64` used to map source offsets to the native and wasm code https://github.com/tetratelabs/wazero/blob/main/internal/engine/compiler/engine.go#L1566-L1572

I modified the data structure to use a version of frame-of-reference and delta encoding described in https://lemire.me/blog/2012/02/08/effective-compression-using-frame-of-reference-and-delta-coding/

The data structure works well in this case because the values of code offsets are often close by, and since we don't reorder instructions, the offsets are naturally sorted. Ordering is important here, if the offsets were reordered the deltas between consecutive values would overflow, preventing values from being stored in small integers. If we end up reordering instructions (or if we are already doing it and I missed it, please let me know!) we could consider implementing more advanced delta encodings such as the one used in [Parquet](https://github.com/apache/parquet-format/blob/master/Encodings.md#delta-encoding-delta_binary_packed--5) which handles negative deltas by subtracting the min value to the array, etc... this is work for another day!

The result seems effective, removing another ~45MB of memory allocated when compiling Python:

```
Type: alloc_space
Time: May 14, 2023 at 11:26pm (PDT)
Showing nodes accounting for -47.51MB, 17.69% of 268.61MB total
Dropped 6 nodes (cum <= 1.34MB)
      flat  flat%   sum%        cum   cum%
  -43.05MB 16.03% 16.03%   -44.17MB 16.44%  github.com/tetratelabs/wazero/internal/engine/compiler.compileWasmFunction
   -5.55MB  2.07% 18.09%    -5.55MB  2.07%  github.com/tetratelabs/wazero/internal/asm/arm64.(*nodePool).allocNode (inline)
    5.06MB  1.88% 16.21%     5.06MB  1.88%  github.com/tetratelabs/wazero/internal/bitpack.newDeltaArray[...] (inline)
      -3MB  1.12% 17.33%       -3MB  1.12%  debug/dwarf.(*Data).parseAbbrev
      -2MB  0.75% 18.07%       -2MB  0.75%  github.com/tetratelabs/wazero/internal/engine/compiler.(*runtimeValueLocationStack).push (inline)
   -1.27MB  0.47% 18.55%   -43.96MB 16.37%  github.com/tetratelabs/wazero/internal/engine/compiler.(*engine).CompileModule
      -1MB  0.37% 18.92%    -1.50MB  0.56%  github.com/tetratelabs/wazero/internal/wasm/binary.decodeDataSegment
    0.53MB   0.2% 18.72%     0.95MB  0.36%  github.com/tetratelabs/wazero/internal/wazeroir.(*Compiler).handleInstruction
    0.52MB   0.2% 18.53%     0.52MB   0.2%  github.com/tetratelabs/wazero/internal/wasm.(*Module).AllDeclarations
    0.50MB  0.19% 18.34%     0.50MB  0.19%  github.com/tetratelabs/wazero/internal/wasm.(*Module).declaredFunctionIndexes
   -0.50MB  0.19% 18.53%    -0.50MB  0.19%  github.com/tetratelabs/wazero/internal/wazeroir.(*controlFrames).push (inline)
   -0.50MB  0.19% 18.71%    -0.50MB  0.19%  github.com/tetratelabs/wazero/internal/wasm/binary.decodeConstantExpression
    0.50MB  0.19% 18.53%     0.50MB  0.19%  github.com/tetratelabs/wazero/internal/wazeroir.(*funcTypeToIRSignatures).get
    0.50MB  0.19% 18.34%     0.50MB  0.19%  github.com/tetratelabs/wazero/internal/asm/arm64.(*AssemblerImpl).encodeRelativeBranch
    0.49MB  0.18% 18.16%     0.49MB  0.18%  github.com/tetratelabs/wazero/internal/asm/arm64.(*AssemblerImpl).encodeADR
    0.48MB  0.18% 17.98%     0.48MB  0.18%  github.com/tetratelabs/wazero/internal/wasm/binary.decodeCode
    0.42MB  0.16% 17.82%     0.42MB  0.16%  github.com/tetratelabs/wazero/internal/wazeroir.(*Compiler).emit
    0.37MB  0.14% 17.69%     0.37MB  0.14%  bytes.growSlice
```

Please take a look and let me know if you have any questions or feedback!


mathetake: drive-by: how does this compare to packing via leb128?
achille-roussel: That's a good question.

In the tests I ran, all offsets end up being packed into arrays of 8 bits integers, so in this case, leb128 would do a bit worse because we wouldn't be able to use the full 8 bits for small deltas.

I think leb128 could be interesting if the offsets were out of order because we could encode each delta with a variable number of bytes. This would likely cause the prefix sum to become a bit more expensive because we would have to decode the values; it would also possibly prevent SIMD acceleration.

That being said, it's likely that in some cases leb128 encoding could be the right trade-off, it will be interesting to investigate more!
achille-roussel: @codefromthecrypt Besides learning the data structures from the articles I linked, the code itself is authentic and written specifically for wazero, there should be no IP violation 👍 

I added a section in `compiler/RATIONALE.md` about this change, as well as a `TODO` related to optimizing `sort.Search`.

I also did more analysis of the distribution of deltas, and it turned out most were <=15 which creates the opportunity for another specialization of the `OfferArray` type using 4 bits integers to shrink the memory footprint further.

Patch:
diff --git a/internal/asm/amd64/impl.go b/internal/asm/amd64/impl.go
index e2d45a54..a3a1c8dd 100644
--- a/internal/asm/amd64/impl.go
+++ b/internal/asm/amd64/impl.go
@@ -12,35 +12,37 @@ import (
 
 // nodeImpl implements asm.Node for amd64.
 type nodeImpl struct {
-	instruction asm.Instruction
-
-	offsetInBinary asm.NodeOffsetInBinary
-
 	// jumpTarget holds the target node in the linked for the jump-kind instruction.
 	jumpTarget *nodeImpl
-	flag       nodeFlag
+
 	// prev and next hold the prev/next node from this node in the assembled linked list.
 	prev, next *nodeImpl
 
-	types                    operandTypes
-	srcReg, dstReg           asm.Register
-	srcConst, dstConst       asm.ConstantValue
-	srcMemIndex, dstMemIndex asm.Register
-	srcMemScale, dstMemScale byte
+	// forwardJumpOrigins hold all the nodes trying to jump into this node as a
+	// singly linked list. In other words, all the nodes with .jumpTarget == this.
+	forwardJumpOrigins *nodeImpl
+
+	staticConst *asm.StaticConst
 
-	arg byte
+	dstConst       asm.ConstantValue
+	offsetInBinary asm.NodeOffsetInBinary
+	srcConst       asm.ConstantValue
+	instruction    asm.Instruction
 
 	// readInstructionAddressBeforeTargetInstruction holds the instruction right before the target of
 	// read instruction address instruction. See asm.assemblerBase.CompileReadInstructionAddress.
 	readInstructionAddressBeforeTargetInstruction asm.Instruction
+	flag                                          nodeFlag
+	types                                         operandTypes
+	srcReg, dstReg                                asm.Register
+	srcMemIndex, dstMemIndex                      asm.Register
+	srcMemScale, dstMemScale                      byte
+	arg                                           byte
 
-	// forwardJumpOrigins hold all the nodes trying to jump into this node as a singly linked list. In other words, all the nodes with .jumpTarget == this.
-	forwardJumpOrigins *nodeImpl
 	// staticConstReferrersAdded true if this node is already added into AssemblerImpl.staticConstReferrers.
 	// Only used when staticConst is not nil. Through re-assembly, we might end up adding multiple times which causes unnecessary
 	// allocations, so we use this flag to do it once.
 	staticConstReferrersAdded bool
-	staticConst               *asm.StaticConst
 }
 
 type nodeFlag byte
@@ -218,20 +220,24 @@ func (o operandTypes) String() (ret string) {
 type (
 	// AssemblerImpl implements Assembler.
 	AssemblerImpl struct {
-		nodePool nodePool
+		root    *nodeImpl
+		current *nodeImpl
+		buf     *bytes.Buffer
 		asm.BaseAssemblerImpl
-		root, current   *nodeImpl
-		buf             *bytes.Buffer
-		forceReAssemble bool
-		// MaxDisplacementForConstantPool is fixed to defaultMaxDisplacementForConstantPool
-		// but have it as an exported field here for testability.
-		MaxDisplacementForConstantPool int
-
 		readInstructionAddressNodes []*nodeImpl
+
 		// staticConstReferrers maintains the list of static const referrers which requires the
 		// offset resolution after finalizing the binary layout.
 		staticConstReferrers []staticConstReferrer
-		pool                 asm.StaticConstPool
+
+		nodePool nodePool
+		pool     asm.StaticConstPool
+
+		// MaxDisplacementForConstantPool is fixed to defaultMaxDisplacementForConstantPool
+		// but have it as an exported field here for testability.
+		MaxDisplacementForConstantPool int
+
+		forceReAssemble bool
 	}
 
 	// staticConstReferrer represents a referrer of a asm.StaticConst.
diff --git a/internal/asm/arm64/impl.go b/internal/asm/arm64/impl.go
index 69662d14..138cd871 100644
--- a/internal/asm/arm64/impl.go
+++ b/internal/asm/arm64/impl.go
@@ -10,27 +10,25 @@ import (
 )
 
 type nodeImpl struct {
-	instruction asm.Instruction
-
-	offsetInBinaryField asm.NodeOffsetInBinary // Field suffix to dodge conflict with OffsetInBinary
-
 	// jumpTarget holds the target node in the linked for the jump-kind instruction.
 	jumpTarget *nodeImpl
 	// next holds the next node from this node in the assembled linked list.
-	next *nodeImpl
+	next        *nodeImpl
+	staticConst *asm.StaticConst
 
+	instruction                      asm.Instruction
 	types                            operandTypes
 	srcReg, srcReg2, dstReg, dstReg2 asm.Register
 	srcConst, dstConst               asm.ConstantValue
 
-	vectorArrangement              VectorArrangement
-	srcVectorIndex, dstVectorIndex VectorIndex
+	offsetInBinary asm.NodeOffsetInBinary
 
 	// readInstructionAddressBeforeTargetInstruction holds the instruction right before the target of
 	// read instruction address instruction. See asm.assemblerBase.CompileReadInstructionAddress.
 	readInstructionAddressBeforeTargetInstruction asm.Instruction
 
-	staticConst *asm.StaticConst
+	vectorArrangement              VectorArrangement
+	srcVectorIndex, dstVectorIndex VectorIndex
 }
 
 // AssignJumpTarget implements the same method as documented on asm.Node.
@@ -50,7 +48,7 @@ func (n *nodeImpl) AssignSourceConstant(value asm.ConstantValue) {
 
 // OffsetInBinary implements the same method as documented on asm.Node.
 func (n *nodeImpl) OffsetInBinary() asm.NodeOffsetInBinary {
-	return n.offsetInBinaryField
+	return n.offsetInBinary
 }
 
 // String implements fmt.Stringer.
@@ -201,17 +199,21 @@ const (
 
 // AssemblerImpl implements Assembler.
 type AssemblerImpl struct {
-	nodePool nodePool
+	root    *nodeImpl
+	current *nodeImpl
+	buf     *bytes.Buffer
 	asm.BaseAssemblerImpl
-	root, current     *nodeImpl
-	buf               *bytes.Buffer
-	temporaryRegister asm.Register
-	nodeCount         int
-	pool              asm.StaticConstPool
+	relativeJumpNodes   []*nodeImpl
+	adrInstructionNodes []*nodeImpl
+	nodePool            nodePool
+	pool                asm.StaticConstPool
+	nodeCount           int
+
 	// MaxDisplacementForConstantPool is fixed to defaultMaxDisplacementForConstPool
 	// but have it as a field here for testability.
-	MaxDisplacementForConstantPool         int
-	relativeJumpNodes, adrInstructionNodes []*nodeImpl
+	MaxDisplacementForConstantPool int
+
+	temporaryRegister asm.Register
 }
 
 const nodePageSize = 128
@@ -338,7 +340,7 @@ func (a *AssemblerImpl) Assemble() ([]byte, error) {
 	a.buf.Grow(a.nodeCount * 8)
 
 	for n := a.root; n != nil; n = n.next {
-		n.offsetInBinaryField = uint64(a.buf.Len())
+		n.offsetInBinary = uint64(a.buf.Len())
 		if err := a.encodeNode(n); err != nil {
 			return nil, err
 		}
@@ -2876,8 +2878,8 @@ func (a *AssemblerImpl) encodeStaticConstToVectorRegister(n *nodeImpl) (err erro
 // advancedSIMDTwoRegisterMisc holds information to encode instructions as "Advanced SIMD two-register miscellaneous" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDTwoRegisterMisc = map[asm.Instruction]struct {
-	u, opcode byte
 	qAndSize  map[VectorArrangement]qAndSize
+	u, opcode byte
 }{
 	// https://developer.arm.com/documentation/ddi0596/2021-12/SIMD-FP-Instructions/NOT--Bitwise-NOT--vector--?lang=en
 	NOT: {
@@ -3026,8 +3028,8 @@ var advancedSIMDTwoRegisterMisc = map[asm.Instruction]struct {
 // advancedSIMDThreeDifferent holds information to encode instructions as "Advanced SIMD three different" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDThreeDifferent = map[asm.Instruction]struct {
-	u, opcode byte
 	qAndSize  map[VectorArrangement]qAndSize
+	u, opcode byte
 }{
 	// https://developer.arm.com/documentation/ddi0596/2021-12/SIMD-FP-Instructions/UMLAL--UMLAL2--vector---Unsigned-Multiply-Add-Long--vector--?lang=en
 	VUMLAL: {u: 0b1, opcode: 0b1000, qAndSize: map[VectorArrangement]qAndSize{
@@ -3064,8 +3066,8 @@ var advancedSIMDThreeDifferent = map[asm.Instruction]struct {
 // advancedSIMDThreeSame holds information to encode instructions as "Advanced SIMD three same" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDThreeSame = map[asm.Instruction]struct {
-	u, opcode byte
 	qAndSize  map[VectorArrangement]qAndSize
+	u, opcode byte
 }{
 	// https://developer.arm.com/documentation/ddi0596/2021-12/SIMD-FP-Instructions/AND--vector---Bitwise-AND--vector--?lang=en
 	VAND: {
@@ -3273,8 +3275,8 @@ var defaultQAndSize = map[VectorArrangement]qAndSize{
 // advancedSIMDAcrossLanes holds information to encode instructions as "Advanced SIMD across lanes" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDAcrossLanes = map[asm.Instruction]struct {
-	u, opcode byte
 	qAndSize  map[VectorArrangement]qAndSize
+	u, opcode byte
 }{
 	// https://developer.arm.com/documentation/ddi0596/2021-12/SIMD-FP-Instructions/ADDV--Add-across-Vector-?lang=en
 	ADDV: {
@@ -3310,8 +3312,8 @@ var advancedSIMDAcrossLanes = map[asm.Instruction]struct {
 // advancedSIMDScalarPairwise holds information to encode instructions as "Advanced SIMD scalar pairwise" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDScalarPairwise = map[asm.Instruction]struct {
-	u, opcode byte
 	size      map[VectorArrangement]byte
+	u, opcode byte
 }{
 	// https://developer.arm.com/documentation/ddi0596/2021-12/SIMD-FP-Instructions/ADDP--scalar---Add-Pair-of-elements--scalar--?lang=en
 	ADDP: {u: 0b0, opcode: 0b11011, size: map[VectorArrangement]byte{VectorArrangement2D: 0b11}},
@@ -3320,9 +3322,9 @@ var advancedSIMDScalarPairwise = map[asm.Instruction]struct {
 // advancedSIMDCopy holds information to encode instructions as "Advanced SIMD copy" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDCopy = map[asm.Instruction]struct {
-	op byte
 	// TODO: extract common implementation of resolver.
 	resolver func(srcIndex, dstIndex VectorIndex, arr VectorArrangement) (imm5, imm4, q byte, err error)
+	op       byte
 }{
 	// https://developer.arm.com/documentation/ddi0596/2021-12/SIMD-FP-Instructions/DUP--element---Duplicate-vector-element-to-vector-or-scalar-?lang=en
 	DUPELEM: {op: 0, resolver: func(srcIndex, dstIndex VectorIndex, arr VectorArrangement) (imm5, imm4, q byte, err error) {
@@ -3463,8 +3465,8 @@ var advancedSIMDCopy = map[asm.Instruction]struct {
 // advancedSIMDTableLookup holds information to encode instructions as "Advanced SIMD table lookup" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDTableLookup = map[asm.Instruction]struct {
-	op, op2, Len byte
 	q            map[VectorArrangement]byte
+	op, op2, Len byte
 }{
 	TBL1: {op: 0, op2: 0, Len: 0b00, q: map[VectorArrangement]byte{VectorArrangement16B: 0b1, VectorArrangement8B: 0b0}},
 	TBL2: {op: 0, op2: 0, Len: 0b01, q: map[VectorArrangement]byte{VectorArrangement16B: 0b1, VectorArrangement8B: 0b0}},
@@ -3473,9 +3475,9 @@ var advancedSIMDTableLookup = map[asm.Instruction]struct {
 // advancedSIMDShiftByImmediate holds information to encode instructions as "Advanced SIMD shift by immediate" in
 // https://developer.arm.com/documentation/ddi0596/2021-12/Index-by-Encoding/Data-Processing----Scalar-Floating-Point-and-Advanced-SIMD?lang=en
 var advancedSIMDShiftByImmediate = map[asm.Instruction]struct {
-	U, opcode   byte
 	q           map[VectorArrangement]byte
 	immResolver func(shiftAmount int64, arr VectorArrangement) (immh, immb byte, err error)
+	U, opcode   byte
 }{
 	// https://developer.arm.com/documentation/ddi0596/2020-12/SIMD-FP-Instructions/SSHLL--SSHLL2--Signed-Shift-Left-Long--immediate--
 	SSHLL: {
diff --git a/internal/asm/assembler.go b/internal/asm/assembler.go
index 9d2dd79a..79ecfefd 100644
--- a/internal/asm/assembler.go
+++ b/internal/asm/assembler.go
@@ -52,11 +52,12 @@ type ConstantValue = int64
 // StaticConst represents an arbitrary constant bytes which are pooled and emitted by assembler into the binary.
 // These constants can be referenced by instructions.
 type StaticConst struct {
+	// offsetFinalizedCallbacks holds callbacks which are called when .OffsetInBinary is finalized by assembler implementation.
+	offsetFinalizedCallbacks []func(offsetOfConstInBinary uint64)
+
 	Raw []byte
 	// OffsetInBinary is the offset of this static const in the result binary.
 	OffsetInBinary uint64
-	// offsetFinalizedCallbacks holds callbacks which are called when .OffsetInBinary is finalized by assembler implementation.
-	offsetFinalizedCallbacks []func(offsetOfConstInBinary uint64)
 }
 
 // NewStaticConst returns the pointer to the new NewStaticConst for given bytes.
@@ -79,13 +80,14 @@ func (s *StaticConst) SetOffsetInBinary(offset uint64) {
 
 // StaticConstPool holds a bulk of StaticConst which are yet to be emitted into the binary.
 type StaticConstPool struct {
-	// FirstUseOffsetInBinary holds the offset of the first instruction which accesses this const pool .
-	FirstUseOffsetInBinary NodeOffsetInBinary
-	Consts                 []*StaticConst
 	// addedConsts is used to deduplicate the consts to reduce the final size of binary.
 	// Note: we can use map on .consts field and remove this field,
 	// but we have the separate field for deduplication in order to have deterministic assembling behavior.
 	addedConsts map[*StaticConst]struct{}
+
+	Consts []*StaticConst
+	// FirstUseOffsetInBinary holds the offset of the first instruction which accesses this const pool .
+	FirstUseOffsetInBinary NodeOffsetInBinary
 	// PoolSizeInBytes is the current size of the pool in bytes.
 	PoolSizeInBytes int
 }
diff --git a/internal/bitpack/offset_array.go b/internal/bitpack/offset_array.go
new file mode 100644
index 00000000..8cafd188
--- /dev/null
+++ b/internal/bitpack/offset_array.go
@@ -0,0 +1,224 @@
+package bitpack
+
+import (
+	"math"
+)
+
+// OffsetArray is an interface representing read-only views of arrays of 64 bits
+// offsets.
+type OffsetArray interface {
+	// Returns the value at index i.
+	//
+	// The method complexity may be anywhere between O(1) and O(N).
+	Index(i int) uint64
+	// Returns the number of offsets in the array.
+	//
+	// The method complexity must be O(1).
+	Len() int
+}
+
+// OffsetArrayLen is a helper function to access the length of an offset array.
+// It is similar to calling Len on the array but handles the special case where
+// the array is nil, in which case it returns zero.
+func OffsetArrayLen(array OffsetArray) int {
+	if array != nil {
+		return array.Len()
+	}
+	return 0
+}
+
+// NewOffsetArray constructs a new array of offsets from the slice of values
+// passed as argument. The slice is not retained, the returned array always
+// holds a copy of the values.
+//
+// The underlying implementation of the offset array applies a compression
+// mechanism derived from Frame-of-Reference and Delta Encoding to minimize
+// the memory footprint of the array. This compression model works best when
+// the input is made of ordered values, otherwise the deltas between values
+// are likely to be too large to benefit from delta encoding.
+//
+// See https://lemire.me/blog/2012/02/08/effective-compression-using-frame-of-reference-and-delta-coding/
+func NewOffsetArray(values []uint64) OffsetArray {
+	if len(values) == 0 {
+		return emptyOffsetArray{}
+	}
+	if len(values) <= smallOffsetArrayCapacity {
+		return newSmallOffsetArray(values)
+	}
+
+	maxDelta := uint64(0)
+	lastValue := values[0]
+	// TODO: the pre-processing we perform here can be optimized using SIMD
+	// instructions.
+	for _, value := range values[1:] {
+		if delta := value - lastValue; delta > maxDelta {
+			maxDelta = delta
+		}
+		lastValue = value
+	}
+
+	switch {
+	case maxDelta > math.MaxUint32:
+		return newOffsetArray(values)
+	case maxDelta > math.MaxUint16:
+		return newDeltaArray[uint32](values)
+	case maxDelta > math.MaxUint8:
+		return newDeltaArray[uint16](values)
+	case maxDelta > 15:
+		return newDeltaArray[uint8](values)
+	default:
+		return newDeltaArrayUint4(values)
+	}
+}
+
+type offsetArray struct {
+	values []uint64
+}
+
+func newOffsetArray(values []uint64) *offsetArray {
+	a := &offsetArray{
+		values: make([]uint64, len(values)),
+	}
+	copy(a.values, values)
+	return a
+}
+
+func (a *offsetArray) Index(i int) uint64 {
+	return a.values[i]
+}
+
+func (a *offsetArray) Len() int {
+	return len(a.values)
+}
+
+type emptyOffsetArray struct{}
+
+func (emptyOffsetArray) Index(int) uint64 {
+	panic("index out of bounds")
+}
+
+func (emptyOffsetArray) Len() int {
+	return 0
+}
+
+const smallOffsetArrayCapacity = 7
+
+type smallOffsetArray struct {
+	length int
+	values [smallOffsetArrayCapacity]uint64
+}
+
+func newSmallOffsetArray(values []uint64) *smallOffsetArray {
+	a := &smallOffsetArray{length: len(values)}
+	copy(a.values[:], values)
+	return a
+}
+
+func (a *smallOffsetArray) Index(i int) uint64 {
+	if i < 0 || i >= a.length {
+		panic("index out of bounds")
+	}
+	return a.values[i]
+}
+
+func (a *smallOffsetArray) Len() int {
+	return a.length
+}
+
+type uintType interface {
+	uint8 | uint16 | uint32 | uint64
+}
+
+type deltaArray[T uintType] struct {
+	deltas     []T
+	firstValue uint64
+}
+
+func newDeltaArray[T uintType](values []uint64) *deltaArray[T] {
+	a := &deltaArray[T]{
+		deltas:     make([]T, len(values)-1),
+		firstValue: values[0],
+	}
+	lastValue := values[0]
+	for i, value := range values[1:] {
+		a.deltas[i] = T(value - lastValue)
+		lastValue = value
+	}
+	return a
+}
+
+func (a *deltaArray[T]) Index(i int) uint64 {
+	if i < 0 || i >= a.Len() {
+		panic("index out of bounds")
+	}
+	value := a.firstValue
+	// TODO: computing the prefix sum can be vectorized;
+	// see https://en.algorithmica.org/hpc/algorithms/prefix/
+	for _, delta := range a.deltas[:i] {
+		value += uint64(delta)
+	}
+	return value
+}
+
+func (a *deltaArray[T]) Len() int {
+	return len(a.deltas) + 1
+}
+
+// deltaArrayUint4 is a specialization of deltaArray which packs 4 bits integers
+// to hold deltas between 0 and 15; based on the analysis of compiling Python,
+// it appeared that most source offset deltas were under 16, so using this
+// data structure cuts by 50% the memory needed compared to deltaArray[uint8].
+//
+// Here is the distribution of source offset deltas for Python 3.13:
+//
+// - <=15    : 10240
+// - <=255   : 9565
+// - <=65535 : 1163
+//
+// Memory profiles showed that using deltaArrayUint4 (compared to deltaArray[T])
+// dropped the memory footprint of source mappings for Python from 6MB to 4.5MB.
+type deltaArrayUint4 struct {
+	deltas     []byte
+	numValues  int
+	firstValue uint64
+}
+
+func newDeltaArrayUint4(values []uint64) *deltaArrayUint4 {
+	a := &deltaArrayUint4{
+		deltas:     make([]byte, len(values)/2+1),
+		numValues:  len(values),
+		firstValue: values[0],
+	}
+	lastValue := values[0]
+	for i, value := range values[1:] {
+		a.assign(i, value-lastValue)
+		lastValue = value
+	}
+	return a
+}
+
+func (a *deltaArrayUint4) assign(i int, v uint64) {
+	index, shift := uint(i)>>1, 4*(uint(i)&1)
+	a.deltas[index] &= ^(0xF << shift)
+	a.deltas[index] |= byte(v) << shift
+}
+
+func (a *deltaArrayUint4) index(i int) uint64 {
+	index, shift := uint(i)>>1, 4*(uint(i)&1)
+	return uint64((a.deltas[index] >> shift) & 0xF)
+}
+
+func (a *deltaArrayUint4) Index(i int) uint64 {
+	if i < 0 || i >= a.Len() {
+		panic("index out of bounds")
+	}
+	value := a.firstValue
+	for j := 0; j < i; j++ {
+		value += a.index(j)
+	}
+	return value
+}
+
+func (a *deltaArrayUint4) Len() int {
+	return a.numValues
+}
diff --git a/internal/engine/compiler/RATIONALE.md b/internal/engine/compiler/RATIONALE.md
index 2db59e72..9cb7513e 100644
--- a/internal/engine/compiler/RATIONALE.md
+++ b/internal/engine/compiler/RATIONALE.md
@@ -91,3 +91,22 @@ cancellation from taking place.
 
 [checkexitcode_loop]: https://github.com/tetratelabs/wazero/blob/86444c67a37dbf9e693ae5b365901f64968d9025/internal/wazeroir/compiler.go#L467-L476
 [native_check]: https://github.com/tetratelabs/wazero/issues/1409
+
+## Source Offset Mapping
+
+When translating code from WebAssembly to the wazero IR, and compiling to native
+binary, wazero keeps track of two indexes to correlate native program counters
+to the original source offset that they were generated from.
+
+Source offset maps are useful for debugging, but holding indexes in memory for
+all instructions can have a significant overhead. To reduce the memory footprint
+of the compiled modules, wazero uses data structures inspired by
+[frame-of-reference and delta encoding][FOR].
+
+Because wazero does not reorder instructions, the source offsets are naturally
+sorted during compilation, and the distance between two consecutive offsets is
+usually small. Encoding deltas instead of the absolute values allows most of
+the indexes to store offsets with an overhead of 8 bits per instruction, instead
+of recording 64 bits integers for absolute code positions.
+
+[FOR]: https://lemire.me/blog/2012/02/08/effective-compression-using-frame-of-reference-and-delta-coding/
diff --git a/internal/engine/compiler/engine.go b/internal/engine/compiler/engine.go
index 62d48084..5f43ff22 100644
--- a/internal/engine/compiler/engine.go
+++ b/internal/engine/compiler/engine.go
@@ -13,6 +13,7 @@ import (
 	"github.com/tetratelabs/wazero/api"
 	"github.com/tetratelabs/wazero/experimental"
 	"github.com/tetratelabs/wazero/internal/asm"
+	"github.com/tetratelabs/wazero/internal/bitpack"
 	"github.com/tetratelabs/wazero/internal/filecache"
 	"github.com/tetratelabs/wazero/internal/internalapi"
 	"github.com/tetratelabs/wazero/internal/platform"
@@ -285,17 +286,27 @@ type (
 		sourceOffsetMap sourceOffsetMap
 	}
 
-	// sourceOffsetMap holds the information to retrieve the original offset in the Wasm binary from the
-	// offset in the native binary.
+	// sourceOffsetMap holds the information to retrieve the original offset in
+	// the Wasm binary from the offset in the native binary.
+	//
+	// The fields are implemented as bit-packed arrays of 64 bits integers to
+	// reduce the memory footprint. Indexing into such arrays is not as fast as
+	// indexing into a simple slice, but the source offset map is intended to be
+	// used for debugging, lookups into the arrays should not appear on code
+	// paths that are critical to the application performance.
+	//
+	// The bitpack.OffsetArray fields may be nil, use bitpack.OffsetArrayLen to
+	// determine whether they are empty prior to indexing into the arrays to
+	// avoid panics caused by accessing nil pointers.
 	sourceOffsetMap struct {
 		// See note at top of file before modifying this struct.
 
 		// irOperationOffsetsInNativeBinary is index-correlated with irOperationSourceOffsetsInWasmBinary,
 		// and maps each index (corresponding to each IR Operation) to the offset in the compiled native code.
-		irOperationOffsetsInNativeBinary []uint64
+		irOperationOffsetsInNativeBinary bitpack.OffsetArray
 		// irOperationSourceOffsetsInWasmBinary is index-correlated with irOperationOffsetsInNativeBinary.
 		// See wazeroir.CompilationResult irOperationOffsetsInNativeBinary.
-		irOperationSourceOffsetsInWasmBinary []uint64
+		irOperationSourceOffsetsInWasmBinary bitpack.OffsetArray
 	}
 
 	// functionListenerInvocation captures arguments needed to perform function
@@ -525,6 +536,7 @@ func (e *engine) CompileModule(_ context.Context, module *wasm.Module, listeners
 	ln := len(listeners)
 	cmp := newCompiler()
 	asmNodes := new(asmNodes)
+	offsets := new(offsets)
 
 	// The executable code is allocated in memory mappings of executableLength,
 	// and grown on demand when we exhaust the memory mapping capacity.
@@ -573,7 +585,7 @@ func (e *engine) CompileModule(_ context.Context, module *wasm.Module, listeners
 			}
 			cmp.Init(typ, ir, lsn != nil)
 
-			body, compiledFn.stackPointerCeil, compiledFn.sourceOffsetMap, err = compileWasmFunction(cmp, ir, asmNodes)
+			body, compiledFn.stackPointerCeil, compiledFn.sourceOffsetMap, err = compileWasmFunction(cmp, ir, asmNodes, offsets)
 			if err != nil {
 				def := module.FunctionDefinition(funcIndex + importedFuncs)
 				return fmt.Errorf("error compiling wasm func[%s]: %w", def.DebugName(), err)
@@ -851,7 +863,7 @@ func (ce *callEngine) deferredOnCall(ctx context.Context, m *wasm.ModuleInstance
 			// It is not empty only when the DWARF is enabled.
 			var sources []string
 			if p := fn.parent; p.parent.executable != nil {
-				if len(fn.parent.sourceOffsetMap.irOperationSourceOffsetsInWasmBinary) != 0 {
+				if fn.parent.sourceOffsetMap.irOperationSourceOffsetsInWasmBinary != nil {
 					offset := fn.getSourceOffsetInWasmBinary(pc)
 					sources = p.parent.source.DWARFLines.Line(offset)
 				}
@@ -895,31 +907,41 @@ func (ce *callEngine) deferredOnCall(ctx context.Context, m *wasm.ModuleInstance
 // If needPreviousInstr equals true, this returns the previous instruction's offset for the given pc.
 func (f *function) getSourceOffsetInWasmBinary(pc uint64) uint64 {
 	srcMap := &f.parent.sourceOffsetMap
-	n := len(srcMap.irOperationOffsetsInNativeBinary) + 1
+	n := bitpack.OffsetArrayLen(srcMap.irOperationOffsetsInNativeBinary) + 1
 
 	// Calculate the offset in the compiled native binary.
 	pcOffsetInNativeBinary := pc - uint64(f.codeInitialAddress)
 
-	// Then, do the binary search on the list of offsets in the native binary for all the IR operations.
-	// This returns the index of the *next* IR operation of the one corresponding to the origin of this pc.
+	// Then, do the binary search on the list of offsets in the native binary
+	// for all the IR operations. This returns the index of the *next* IR
+	// operation of the one corresponding to the origin of this pc.
 	// See sort.Search.
+	//
+	// TODO: the underlying implementation of irOperationOffsetsInNativeBinary
+	// uses uses delta encoding an calls to the Index method might require a
+	// O(N)  scan of the underlying array, turning binary search into a
+	// O(N*log(N)) operation. If this code path ends up being a bottleneck,
+	// we could add a Search method on the bitpack.OffsetArray types to delegate
+	// the lookup to the underlying data structure, allowing for the selection
+	// of a more optimized version of the algorithm. If you do so, please add a
+	// benchmark to verify the impact on compute time.
 	index := sort.Search(n, func(i int) bool {
 		if i == n-1 {
 			return true
 		}
-		return srcMap.irOperationOffsetsInNativeBinary[i] >= pcOffsetInNativeBinary
+		return srcMap.irOperationOffsetsInNativeBinary.Index(i) >= pcOffsetInNativeBinary
 	})
-	if index == 0 && len(srcMap.irOperationSourceOffsetsInWasmBinary) > 0 {
+	if index == 0 && bitpack.OffsetArrayLen(srcMap.irOperationSourceOffsetsInWasmBinary) > 0 {
 		// When pc is the beginning of the function, the next IR
 		// operation (returned by sort.Search) is the first of the
 		// offset map.
-		return srcMap.irOperationSourceOffsetsInWasmBinary[0]
+		return srcMap.irOperationSourceOffsetsInWasmBinary.Index(0)
 	}
 
 	if index == n || index == 0 { // This case, somehow pc is not found in the source offset map.
 		return 0
 	} else {
-		return srcMap.irOperationSourceOffsetsInWasmBinary[index-1]
+		return srcMap.irOperationSourceOffsetsInWasmBinary.Index(index - 1)
 	}
 }
 
@@ -1198,7 +1220,7 @@ func (f internalFunction) Definition() api.FunctionDefinition {
 // SourceOffsetForPC implements the same method as documented on experimental.InternalFunction.
 func (f internalFunction) SourceOffsetForPC(pc experimental.ProgramCounter) uint64 {
 	p := f.parent
-	if len(p.sourceOffsetMap.irOperationSourceOffsetsInWasmBinary) == 0 {
+	if bitpack.OffsetArrayLen(p.sourceOffsetMap.irOperationSourceOffsetsInWasmBinary) == 0 {
 		return 0 // source not available
 	}
 	return f.getSourceOffsetInWasmBinary(uint64(pc))
@@ -1232,7 +1254,11 @@ type asmNodes struct {
 	nodes []asm.Node
 }
 
-func compileWasmFunction(cmp compiler, ir *wazeroir.CompilationResult, asmNodes *asmNodes) (body []byte, spCeil uint64, sm sourceOffsetMap, err error) {
+type offsets struct {
+	values []uint64
+}
+
+func compileWasmFunction(cmp compiler, ir *wazeroir.CompilationResult, asmNodes *asmNodes, offsets *offsets) (body []byte, spCeil uint64, sm sourceOffsetMap, err error) {
 	if err = cmp.compilePreamble(); err != nil {
 		err = fmt.Errorf("failed to emit preamble: %w", err)
 		return
@@ -1563,13 +1589,13 @@ func compileWasmFunction(cmp compiler, ir *wazeroir.CompilationResult, asmNodes
 	}
 
 	if needSourceOffsets {
-		offsetInNativeBin := make([]uint64, len(irOpBegins))
+		offsetInNativeBin := append(offsets.values[:0], make([]uint64, len(irOpBegins))...)
+		offsets.values = offsetInNativeBin
 		for i, nop := range irOpBegins {
 			offsetInNativeBin[i] = nop.OffsetInBinary()
 		}
-		sm.irOperationOffsetsInNativeBinary = offsetInNativeBin
-		sm.irOperationSourceOffsetsInWasmBinary = make([]uint64, len(ir.IROperationSourceOffsetsInWasmBinary))
-		copy(sm.irOperationSourceOffsetsInWasmBinary, ir.IROperationSourceOffsetsInWasmBinary)
+		sm.irOperationOffsetsInNativeBinary = bitpack.NewOffsetArray(offsetInNativeBin)
+		sm.irOperationSourceOffsetsInWasmBinary = bitpack.NewOffsetArray(ir.IROperationSourceOffsetsInWasmBinary)
 	}
 	return
 }


Test patch:
diff --git a/internal/asm/arm64/impl_1_test.go b/internal/asm/arm64/impl_1_test.go
index 68cf8034..c3696fec 100644
--- a/internal/asm/arm64/impl_1_test.go
+++ b/internal/asm/arm64/impl_1_test.go
@@ -589,9 +589,11 @@ func Test_CompileStaticConstToRegister(t *testing.T) {
 
 func Test_checkRegisterToRegisterType(t *testing.T) {
 	tests := []struct {
-		src, dst                     asm.Register
-		requireSrcInt, requireDstInt bool
-		expErr                       string
+		expErr        string
+		src           asm.Register
+		dst           asm.Register
+		requireSrcInt bool
+		requireDstInt bool
 	}{
 		{src: RegR10, dst: RegR30, requireSrcInt: true, requireDstInt: true, expErr: ""},
 		{src: RegR10, dst: RegR30, requireSrcInt: false, requireDstInt: true, expErr: "src requires float register but got R10"},
@@ -652,8 +654,8 @@ func TestAssemblerImpl_encodeNoneToNone(t *testing.T) {
 
 func Test_validateMemoryOffset(t *testing.T) {
 	tests := []struct {
-		offset int64
 		expErr string
+		offset int64
 	}{
 		{offset: 0},
 		{offset: -256},
@@ -1065,13 +1067,15 @@ func TestAssemblerImpl_EncodeMemoryToVectorRegister(t *testing.T) {
 
 func TestAssemblerImpl_EncodeVectorRegisterToVectorRegister(t *testing.T) {
 	tests := []struct {
-		name               string
-		x1, x2             asm.Register
-		inst               asm.Instruction
-		c                  asm.ConstantValue
-		arr                VectorArrangement
-		srcIndex, dstIndex VectorIndex
-		exp                []byte
+		name     string
+		exp      []byte
+		c        asm.ConstantValue
+		inst     asm.Instruction
+		x1       asm.Register
+		x2       asm.Register
+		arr      VectorArrangement
+		srcIndex VectorIndex
+		dstIndex VectorIndex
 	}{
 		{
 			inst: XTN,
@@ -2818,8 +2822,8 @@ func TestAssemblerImpl_EncodeThreeRegistersToRegister(t *testing.T) {
 
 	tests := []struct {
 		name string
-		inst asm.Instruction
 		exp  []byte
+		inst asm.Instruction
 	}{
 		{
 			name: "MSUB/src1=R1,src2=R10,src3=R30,dst=R11",
@@ -3988,9 +3992,9 @@ func TestAssemblerImpl_encodeADR_staticConst(t *testing.T) {
 
 	tests := []struct {
 		name                   string
-		reg                    asm.Register
-		offsetOfConstInBinary  uint64
 		expADRInstructionBytes []byte
+		offsetOfConstInBinary  uint64
+		reg                    asm.Register
 	}{
 		{
 			// #8 = offsetOfConstInBinary - beforeADRByteNum.
diff --git a/internal/asm/arm64/impl_3_test.go b/internal/asm/arm64/impl_3_test.go
index 4a1d398c..6852272f 100644
--- a/internal/asm/arm64/impl_3_test.go
+++ b/internal/asm/arm64/impl_3_test.go
@@ -32,10 +32,12 @@ func TestAssemblerImpl_EncodeTwoRegistersToRegister(t *testing.T) {
 	})
 
 	tests := []struct {
-		name           string
-		inst           asm.Instruction
-		src, src2, dst asm.Register
-		exp            []byte
+		name string
+		exp  []byte
+		inst asm.Instruction
+		src  asm.Register
+		src2 asm.Register
+		dst  asm.Register
 	}{
 		{name: "src=RZR,src2=RZR,dst=RZR", inst: AND, src: RegRZR, src2: RegRZR, dst: RegRZR, exp: []byte{0xff, 0x3, 0x1f, 0x8a}},
 		{name: "src=RZR,src2=RZR,dst=R10", inst: AND, src: RegRZR, src2: RegRZR, dst: RegR10, exp: []byte{0xea, 0x3, 0x1f, 0x8a}},
@@ -646,10 +648,10 @@ func TestAssemblerImpl_EncodeRegisterAndConstToNone(t *testing.T) {
 
 	tests := []struct {
 		name string
+		exp  []byte
+		c    int64
 		inst asm.Instruction
 		reg  asm.Register
-		c    int64
-		exp  []byte
 	}{
 		{name: "R1, 0", inst: CMP, reg: RegR1, c: 0, exp: []byte{0x3f, 0x0, 0x0, 0xf1}},
 		{name: "R1, 10", inst: CMP, reg: RegR1, c: 10, exp: []byte{0x3f, 0x28, 0x0, 0xf1}},
@@ -704,10 +706,11 @@ func TestAssemblerImpl_EncodeRegisterToRegister(t *testing.T) {
 	})
 
 	tests := []struct {
-		name     string
-		inst     asm.Instruction
-		src, dst asm.Register
-		exp      []byte
+		name string
+		exp  []byte
+		inst asm.Instruction
+		src  asm.Register
+		dst  asm.Register
 	}{
 		{name: "MOV/src=RegSP,dst=R10", inst: MOVD, src: RegSP, dst: RegR10, exp: []byte{0xea, 0x3, 0x0, 0x91}},
 		{name: "MOV/src=RegSP,dst=R30", inst: MOVD, src: RegSP, dst: RegR30, exp: []byte{0xfe, 0x3, 0x0, 0x91}},
diff --git a/internal/asm/arm64/impl_4_test.go b/internal/asm/arm64/impl_4_test.go
index 27de54e6..d54fbc8e 100644
--- a/internal/asm/arm64/impl_4_test.go
+++ b/internal/asm/arm64/impl_4_test.go
@@ -40,9 +40,9 @@ func TestAssemblerImpl_encodeJumpToRegister(t *testing.T) {
 
 	tests := []struct {
 		name   string
+		expHex string
 		inst   asm.Instruction
 		reg    asm.Register
-		expHex string
 	}{
 		{
 			name:   "B",
@@ -665,8 +665,8 @@ func TestAssemblerImpl_encodeReadInstructionAddress(t *testing.T) {
 	t.Run("ok", func(t *testing.T) {
 		tests := []struct {
 			name                   string
-			numDummyInstructions   int
 			expADRInstructionBytes []byte
+			numDummyInstructions   int
 		}{
 			{
 				name:                   "< 8-bit offset",
@@ -718,7 +718,7 @@ func TestAssemblerImpl_encodeReadInstructionAddress(t *testing.T) {
 					actual[pos:pos+4], hex.EncodeToString(actual))
 
 				require.Equal(t, uint64(4+tc.numDummyInstructions*4+4),
-					target.offsetInBinaryField-adrInst.offsetInBinaryField)
+					target.offsetInBinary-adrInst.offsetInBinary)
 			})
 		}
 	})
@@ -744,14 +744,14 @@ func TestAssemblerImpl_encodeReadInstructionAddress(t *testing.T) {
 				a.CompileConstToRegister(MOVD, 1000, RegR10)
 
 				for n := a.root; n != nil; n = n.next {
-					n.offsetInBinaryField = uint64(a.buf.Len())
+					n.offsetInBinary = uint64(a.buf.Len())
 
 					err := a.encodeNode(n)
 					require.NoError(t, err)
 				}
 
 				targetNode := a.current
-				targetNode.offsetInBinaryField = u64
+				targetNode.offsetInBinary = u64
 
 				n := a.adrInstructionNodes[0]
 				err := a.finalizeADRInstructionNode(nil, n)
diff --git a/internal/asm/arm64/impl_6_test.go b/internal/asm/arm64/impl_6_test.go
index 4c678755..45d16c6d 100644
--- a/internal/asm/arm64/impl_6_test.go
+++ b/internal/asm/arm64/impl_6_test.go
@@ -35,7 +35,7 @@ func TestAssemblerImpl_EncodeRelativeJump(t *testing.T) {
 			tc := tt
 			t.Run(tc.name, func(t *testing.T) {
 				a := NewAssembler(asm.NilRegister)
-				n := &nodeImpl{instruction: tc.inst, types: operandTypesNoneToBranch, offsetInBinaryField: 0, jumpTarget: &nodeImpl{offsetInBinaryField: tc.offset}}
+				n := &nodeImpl{instruction: tc.inst, types: operandTypesNoneToBranch, offsetInBinary: 0, jumpTarget: &nodeImpl{offsetInBinary: tc.offset}}
 				err := a.encodeRelativeBranch(n)
 				require.NoError(t, err)
 				_, err = a.Assemble()
@@ -58,11 +58,11 @@ func TestAssemblerImpl_EncodeRelativeJump(t *testing.T) {
 				expErr: "SUB is unsupported for NoneToBranch type",
 			},
 			{
-				n:      &nodeImpl{instruction: B, types: operandTypesNoneToBranch, offsetInBinaryField: 0, jumpTarget: &nodeImpl{offsetInBinaryField: uint64(maxSignedInt26)*4 + 4}},
+				n:      &nodeImpl{instruction: B, types: operandTypesNoneToBranch, offsetInBinary: 0, jumpTarget: &nodeImpl{offsetInBinary: uint64(maxSignedInt26)*4 + 4}},
 				expErr: fmt.Sprintf("relative jump offset %d/4 must be within %d and %d", maxSignedInt26*4+4, minSignedInt26, maxSignedInt26),
 			},
 			{
-				n:      &nodeImpl{instruction: BCONDEQ, types: operandTypesNoneToBranch, offsetInBinaryField: 0, jumpTarget: &nodeImpl{offsetInBinaryField: uint64(maxSignedInt19)*4 + 4}},
+				n:      &nodeImpl{instruction: BCONDEQ, types: operandTypesNoneToBranch, offsetInBinary: 0, jumpTarget: &nodeImpl{offsetInBinary: uint64(maxSignedInt19)*4 + 4}},
 				expErr: fmt.Sprintf("BUG: relative jump offset %d/4(=%d) must be within %d and %d", maxSignedInt19*4+4, maxSignedInt19+1, minSignedInt19, maxSignedInt19),
 			},
 		}
@@ -83,11 +83,13 @@ func TestAssemblerImpl_EncodeRelativeJump(t *testing.T) {
 	})
 
 	tests := []struct {
-		name                                                                      string
-		inst                                                                      asm.Instruction
-		forward                                                                   bool
-		instructionsInPreamble, instructionsBeforeBranch, instructionsAfterBranch int
-		expHex                                                                    string
+		name                     string
+		expHex                   string
+		instructionsInPreamble   int
+		instructionsBeforeBranch int
+		instructionsAfterBranch  int
+		inst                     asm.Instruction
+		forward                  bool
 	}{
 		{name: "B/forward=true(before=0,after=10)", inst: B, forward: true, instructionsInPreamble: 0, instructionsBeforeBranch: 0, instructionsAfterBranch: 10, expHex: "0b0000140a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d2"},
 		{name: "B/forward=true(before=10,after=10)", inst: B, forward: true, instructionsInPreamble: 0, instructionsBeforeBranch: 10, instructionsAfterBranch: 10, expHex: "0a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20b0000140a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d20a7d80d2"},
diff --git a/internal/bitpack/offset_array_test.go b/internal/bitpack/offset_array_test.go
new file mode 100644
index 00000000..f1d187e3
--- /dev/null
+++ b/internal/bitpack/offset_array_test.go
@@ -0,0 +1,34 @@
+package bitpack_test
+
+import (
+	"fmt"
+	"math"
+	"testing"
+
+	"github.com/tetratelabs/wazero/internal/bitpack"
+	"github.com/tetratelabs/wazero/internal/testing/require"
+)
+
+func TestOffsetArray(t *testing.T) {
+	tests := [][]uint64{
+		{},
+		{0},
+		{1, 2, 3, 4, 5, 6, 7, 8, 9},
+		{16: 1},
+		{17: math.MaxUint16 + 1},
+		{21: 10, 22: math.MaxUint16},
+		{0: 42, 100: math.MaxUint64},
+		{0: 42, 1: math.MaxUint32, 101: math.MaxUint64},
+	}
+
+	for _, test := range tests {
+		t.Run(fmt.Sprintf("len=%d", len(test)), func(t *testing.T) {
+			array := bitpack.NewOffsetArray(test)
+			require.Equal(t, len(test), array.Len())
+
+			for i, v := range test {
+				require.Equal(t, v, array.Index(i))
+			}
+		})
+	}
+}
diff --git a/internal/engine/compiler/engine_test.go b/internal/engine/compiler/engine_test.go
index 302bb1a0..b77bc22b 100644
--- a/internal/engine/compiler/engine_test.go
+++ b/internal/engine/compiler/engine_test.go
@@ -12,6 +12,7 @@ import (
 	"github.com/tetratelabs/wazero/api"
 	"github.com/tetratelabs/wazero/experimental"
 	"github.com/tetratelabs/wazero/experimental/logging"
+	"github.com/tetratelabs/wazero/internal/bitpack"
 	"github.com/tetratelabs/wazero/internal/platform"
 	"github.com/tetratelabs/wazero/internal/testing/enginetest"
 	"github.com/tetratelabs/wazero/internal/testing/require"
@@ -671,12 +672,12 @@ func TestFunction_getSourceOffsetInWasmBinary(t *testing.T) {
 			pc:                 4000,
 			codeInitialAddress: 3999,
 			srcMap: sourceOffsetMap{
-				irOperationOffsetsInNativeBinary: []uint64{
+				irOperationOffsetsInNativeBinary: bitpack.NewOffsetArray([]uint64{
 					0 /*4000-3999=1 exists here*/, 5, 8, 15,
-				},
-				irOperationSourceOffsetsInWasmBinary: []uint64{
+				}),
+				irOperationSourceOffsetsInWasmBinary: bitpack.NewOffsetArray([]uint64{
 					10, 100, 800, 12344,
-				},
+				}),
 			},
 			exp: 10,
 		},
@@ -685,12 +686,12 @@ func TestFunction_getSourceOffsetInWasmBinary(t *testing.T) {
 			pc:                 100,
 			codeInitialAddress: 90,
 			srcMap: sourceOffsetMap{
-				irOperationOffsetsInNativeBinary: []uint64{
+				irOperationOffsetsInNativeBinary: bitpack.NewOffsetArray([]uint64{
 					0, 5, 8 /*100-90=10 exists here*/, 15,
-				},
-				irOperationSourceOffsetsInWasmBinary: []uint64{
+				}),
+				irOperationSourceOffsetsInWasmBinary: bitpack.NewOffsetArray([]uint64{
 					10, 100, 800, 12344,
-				},
+				}),
 			},
 			exp: 800,
 		},
@@ -699,12 +700,12 @@ func TestFunction_getSourceOffsetInWasmBinary(t *testing.T) {
 			pc:                 9999,
 			codeInitialAddress: 8999,
 			srcMap: sourceOffsetMap{
-				irOperationOffsetsInNativeBinary: []uint64{
+				irOperationOffsetsInNativeBinary: bitpack.NewOffsetArray([]uint64{
 					0, 5, 8, 15, /*9999-8999=1000 exists here*/
-				},
-				irOperationSourceOffsetsInWasmBinary: []uint64{
+				}),
+				irOperationSourceOffsetsInWasmBinary: bitpack.NewOffsetArray([]uint64{
 					10, 100, 800, 12344,
-				},
+				}),
 			},
 			exp: 12344,
 		},