* [PATCH olang v2] arena: optimization: make arena 8 bits aligned
@ 2024-02-21 15:09 Carlos Maniero
2024-02-21 15:09 ` [olang/patches/.build.yml] build success builds.sr.ht
2024-02-22 18:50 ` [PATCH olang v2] arena: optimization: make arena 8 bits aligned Johnny Richard
0 siblings, 2 replies; 4+ messages in thread
From: Carlos Maniero @ 2024-02-21 15:09 UTC (permalink / raw)
To: ~johnnyrichard/olang-devel; +Cc: 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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2024-02-28 14:04 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-02-21 15:09 [PATCH olang v2] arena: optimization: make arena 8 bits aligned Carlos Maniero
2024-02-21 15:09 ` [olang/patches/.build.yml] build success builds.sr.ht
2024-02-22 18:50 ` [PATCH olang v2] arena: optimization: make arena 8 bits aligned Johnny Richard
2024-02-28 14:04 ` Carlos Maniero
Code repositories for project(s) associated with this public inbox
https://git.johnnyrichard.com/olang.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox