[PATCH olang] arena: optimization: make arena 8 bits aligned

[PATCH olang] arena: optimization: make arena 8 bits aligned

[Carlos Maniero]

Non aligned data structure could have a huge impact on performance. Take
the example bellow:

  int main() {
      void *pointer = malloc(1024);

      int* data = pointer + 1;

      for (int i = 0; i < INT_MAX; i++) {
          *data += i;
      }

      printf("result = %d", *data);
  }

This are the execution results in my machine:

  pointer + 0
  time	0m1.668s
  pointer + 1
  time	0m2.285s
  pointer + 2
  time	0m2.286s
  pointer + 4
  time	0m1.722s
  pointer + 8
  time	0m1.707s

This commit changes the pointers to always return a 8 bit aligned
pointer.

Signed-off-by: Carlos Maniero <carlos@maniero.me>
---
 src/arena.c             | 2 +-
 tests/unit/arena_test.c | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/src/arena.c b/src/arena.c
index ae33e6a..63662e3 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -35,7 +35,7 @@ arena_alloc(arena_t *arena, size_t size)
         return NULL;
     }
     void *pointer = arena->region + arena->offset;
-    arena->offset += size;
+    arena->offset += size + (size % 8);
     return pointer;
 }
 
diff --git a/tests/unit/arena_test.c b/tests/unit/arena_test.c
index 6310795..7808b64 100644
--- a/tests/unit/arena_test.c
+++ b/tests/unit/arena_test.c
@@ -21,7 +21,7 @@
 static MunitResult
 arena_test(const MunitParameter params[], void *user_data_or_fixture)
 {
-    arena_t arena = arena_new(sizeof(int) * 2);
+    arena_t arena = arena_new(16);
 
     int *a = arena_alloc(&arena, sizeof(int));
     *a = 1;
-- 
2.34.1

[olang/patches/.build.yml] build success

[builds.sr.ht]

olang/patches/.build.yml: SUCCESS in 35s

[arena: optimization: make arena 8 bits aligned][0] from [Carlos Maniero][1]

[0]: https://lists.sr.ht/~johnnyrichard/olang-devel/patches/49718
[1]: mailto:carlos@maniero.me

✓ #1154549 SUCCESS olang/patches/.build.yml https://builds.sr.ht/~johnnyrichard/job/1154549

Re: [PATCH olang] arena: optimization: make arena 8 bits aligned

[Carlos Maniero]

I sent a v2. There was a bug in the padding function.

Re: [PATCH olang] arena: optimization: make arena 8 bits aligned

[Carlos Maniero]

There is a lot that I learned since I started this patch. First of all,
this patch has a bug.

> +    arena->offset += size + (size % 8);

Let's say the offset is zero and the size is one, we would expect the
new offset to be 8 after the *arena_alloc*, but this code was producing
1 as the new offset.

Furthermore, 8 is not the right memory alignment for x86_64
architectures according Intel's manual:

> 4.1.1 Alignment of Words, Doublewords, Quadwords, and Double Quadwords
> 
> Words, doublewords, and quadwords do not need to be aligned in memory on
> natural boundaries. The natural boundaries for words, doublewords, and
> quadwords are even-numbered addresses, addresses evenly divisible by
> four, and addresses evenly divisible by eight, respectively. However, to
> improve the performance of programs, data structures (especially stacks)
> should be aligned on natural boundaries whenever possible. The reason
> for this is that the processor requires two memory accesses to make an
> unaligned memory access; aligned accesses require only one memory
> access. A word or doubleword operand that crosses a 4-byte boundary or a
> quadword operand that crosses an 8-byte boundary is considered unaligned
> and requires two separate memory bus cycles for access.
> 
> Some instructions that operate on double quadwords require memory
> operands to be aligned on a natural boundary. These instructions
> generate a general-protection exception (#GP) if an unaligned operand is
> specified. A natural boundary for a double quadword is any address
> evenly divisible by 16. Other instructions that operate on double
> quadwords permit unaligned access (without generating a
> general-protection exception). However, additional memory bus cycles
> are required to access unaligned data from memory.

https://cdrdv2.intel.com/v1/dl/getContent/671200

So ideally we must align arena on 16 bits.

I'll send a v3 with theses two things fixed.

Re: [PATCH olang] arena: optimization: make arena 8 bits aligned

[Johnny Richard]

On Tue, Feb 27, 2024 at 08:50:48PM -0300, Carlos Maniero wrote:
> I'll send a v3 with theses two things fixed.

Don't forget to take a look to the comments I've added to the V2.

Other than this, great findings!