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

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

[Carlos Maniero]

This commit changes the pointers returned by *arena_alloc* to always be
system-word aligned.

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);
  }

When data is not word-aligned, the processor is required to execute
multiples load/store operation which makes the program to take almost
twice the time it could take if the data was aligned.

These 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

Signed-off-by: Carlos Maniero <carlos@maniero.me>
---
v2: 
 - There was I bug on the padding logic. I fixed it and tests were
   added.

 src/arena.c             | 16 +++++++++---
 src/arena.h             |  3 +++
 tests/unit/arena_test.c | 56 +++++++++++++++++++++++++++++++++++------
 3 files changed, 65 insertions(+), 10 deletions(-)

diff --git a/src/arena.c b/src/arena.c
index ae33e6a..ad2e535 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -28,14 +28,18 @@ arena_new(size_t size)
     return arena;
 }
 
+static uint8_t
+arena_padding(size_t bytes);
+
 void *
-arena_alloc(arena_t *arena, size_t size)
+arena_alloc(arena_t *arena, size_t bytes)
 {
-    if ((arena->offset + size) > arena->size) {
+    if ((arena->offset + bytes) > arena->size) {
         return NULL;
     }
     void *pointer = arena->region + arena->offset;
-    arena->offset += size;
+    arena->offset += bytes + arena_padding(bytes);
+
     return pointer;
 }
 
@@ -51,3 +55,9 @@ arena_free(arena_t *arena)
     arena->size = 0;
     free(arena->region);
 }
+
+static uint8_t
+arena_padding(size_t bytes)
+{
+    return (ARENA_ALIGNMENT_BYTES - bytes) & ARENA_ALIGNMENT_BYTES_MASK;
+}
diff --git a/src/arena.h b/src/arena.h
index 157165c..37a36aa 100644
--- a/src/arena.h
+++ b/src/arena.h
@@ -19,6 +19,9 @@
 #include <stdint.h>
 #include <stdlib.h>
 
+#define ARENA_ALIGNMENT_BYTES sizeof(intptr_t)
+#define ARENA_ALIGNMENT_BYTES_MASK (ARENA_ALIGNMENT_BYTES - 1)
+
 typedef struct arena
 {
     size_t offset;
diff --git a/tests/unit/arena_test.c b/tests/unit/arena_test.c
index 6310795..b380461 100644
--- a/tests/unit/arena_test.c
+++ b/tests/unit/arena_test.c
@@ -19,14 +19,14 @@
 #include "munit.h"
 
 static MunitResult
-arena_test(const MunitParameter params[], void *user_data_or_fixture)
+arena_alloc_test(const MunitParameter params[], void *user_data_or_fixture)
 {
-    arena_t arena = arena_new(sizeof(int) * 2);
+    arena_t arena = arena_new(ARENA_ALIGNMENT_BYTES * 2);
 
-    int *a = arena_alloc(&arena, sizeof(int));
+    uint8_t *a = arena_alloc(&arena, sizeof(uint8_t));
     *a = 1;
 
-    int *b = arena_alloc(&arena, sizeof(int));
+    uint8_t *b = arena_alloc(&arena, sizeof(uint8_t));
     *b = 2;
 
     munit_assert_int(*a, ==, 1);
@@ -34,7 +34,7 @@ arena_test(const MunitParameter params[], void *user_data_or_fixture)
 
     arena_release(&arena);
 
-    int *c = arena_alloc(&arena, sizeof(int));
+    uint8_t *c = arena_alloc(&arena, sizeof(uint8_t));
     *c = 3;
 
     munit_assert_int(*c, ==, 3);
@@ -49,10 +49,52 @@ arena_test(const MunitParameter params[], void *user_data_or_fixture)
     return MUNIT_OK;
 }
 
-static MunitTest tests[] = { { "/arena_test", arena_test, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+static MunitResult
+arena_padding_test(const MunitParameter params[], void *user_data_or_fixture)
+{
+    arena_t arena = arena_new(512);
+
+    // Allocated bytes is < ARENA_ALIGNMENT_BYTES
+    uint8_t *a = arena_alloc(&arena, sizeof(uint8_t));
+    uint8_t *b = arena_alloc(&arena, sizeof(uint8_t));
+
+    munit_assert_int((b - a) % ARENA_ALIGNMENT_BYTES, ==, 0);
+    munit_assert_int(b - a, ==, ARENA_ALIGNMENT_BYTES);
+
+    arena_release(&arena);
+
+    // Allocated bytes is == ARENA_ALIGNMENT_BYTES
+    a = arena_alloc(&arena, ARENA_ALIGNMENT_BYTES);
+    b = arena_alloc(&arena, sizeof(uint8_t));
+
+    munit_assert_int((b - a) % ARENA_ALIGNMENT_BYTES, ==, 0);
+    munit_assert_int(b - a, ==, ARENA_ALIGNMENT_BYTES);
+
+    arena_release(&arena);
+
+    // Allocated bytes is > ARENA_ALIGNMENT_BYTES
+    a = arena_alloc(&arena, ARENA_ALIGNMENT_BYTES + 1);
+    b = arena_alloc(&arena, sizeof(uint8_t));
+
+    arena_release(&arena);
+
+    // Allocated bytes is > 1 byte (overflow test)
+    a = arena_alloc(&arena, UINT8_MAX + 2);
+    b = arena_alloc(&arena, sizeof(uint8_t));
+
+    munit_assert_int((b - a) % ARENA_ALIGNMENT_BYTES, ==, 0);
+    munit_assert_int(b - a, ==, UINT8_MAX + 1 + ARENA_ALIGNMENT_BYTES);
+
+    arena_free(&arena);
+
+    return MUNIT_OK;
+}
+
+static MunitTest tests[] = { { "/arena_alloc_test", arena_alloc_test, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+                             { "/arena_padding_test", arena_padding_test, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
                              { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL } };
 
-static const MunitSuite suite = { "/cli_test", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE };
+static const MunitSuite suite = { "/arena_test", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE };
 
 int
 main(int argc, char *argv[])
-- 
2.34.1

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

[builds.sr.ht]

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

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

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

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

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

[Johnny Richard]

On Wed, Feb 21, 2024 at 12:09:11PM -0300, Carlos Maniero wrote:
> Subject: [PATCH olang v2] arena: optimization: make arena 8 bits aligned

The patch title is say you are using 8 bits but the implementation is
platform agnostic. 

Perhaps we could change it to:

    arena: ensure aligned memory access

> This commit changes the pointers returned by *arena_alloc* to always be
> system-word aligned.
> 
> Non-aligned data structure could have a huge impact on performance. Take
> the example bellow:

We could also link to a document[1] that explains better the problem like
the kernel one.

[1]: https://www.kernel.org/doc/html/next/_sources/core-api/unaligned-memory-access.rst.txt 
  
> v2: 
>  - There was I bug on the padding logic. I fixed it and tests were
>    added.

Could you please reply to the first patch which bug you have
encountered?

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

[Carlos Maniero]

> The patch title is say you are using 8 bits but the implementation is
> platform agnostic.

I'm sending a new patch enforcing 16 bytes alignment. The only benefit
of having platform agnostic alignment is to save a few bits, which IMO
is not justifiable right now.