From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: mail-a.sr.ht; dkim=pass header.d=maniero.me header.i=@maniero.me Received: from slategray.cherry.relay.mailchannels.net (slategray.cherry.relay.mailchannels.net [23.83.223.169]) by mail-a.sr.ht (Postfix) with ESMTPS id 6FBC4201FE for <~johnnyrichard/olang-devel@lists.sr.ht>; Wed, 21 Feb 2024 15:09:22 +0000 (UTC) X-Sender-Id: hostingeremail|x-authuser|carlos@maniero.me Received: from relay.mailchannels.net (localhost [127.0.0.1]) by relay.mailchannels.net (Postfix) with ESMTP id BEFA176239B for <~johnnyrichard/olang-devel@lists.sr.ht>; Wed, 21 Feb 2024 15:09:20 +0000 (UTC) Received: from nl-srv-smtpout4.hostinger.io (unknown [127.0.0.6]) (Authenticated sender: hostingeremail) by relay.mailchannels.net (Postfix) with ESMTPA id 4EB56761F86 for <~johnnyrichard/olang-devel@lists.sr.ht>; Wed, 21 Feb 2024 15:09:20 +0000 (UTC) X-Sender-Id: hostingeremail|x-authuser|carlos@maniero.me X-MC-Relay: Neutral X-MailChannels-SenderId: hostingeremail|x-authuser|carlos@maniero.me X-MailChannels-Auth-Id: hostingeremail X-Continue-Well-Made: 300bb1f54dc7d892_1708528160598_2552641553 X-MC-Loop-Signature: 1708528160598:2814803794 X-MC-Ingress-Time: 1708528160598 Received: from nl-srv-smtpout4.hostinger.io (nl-srv-smtpout4.hostinger.io [145.14.159.45]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384) by 100.100.244.8 (trex/6.9.2); Wed, 21 Feb 2024 15:09:20 +0000 From: Carlos Maniero DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=maniero.me; s=hostingermail1; t=1708528158; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding; bh=HMG+L/tMXFdjdstoe41nnWxPW4I1ajfiAK9DQaN3Uiw=; b=pnCbpDCKmZuxuX5LGuKGo9wVW1gLMlbnfBfklzVpioqv+q3e4jr9G5EQjCp4QqqNLZscyp LEf1H62VSF26PxYkfS5FMLS5mO1H4tDbp9jXwC2Pj+1sxbEQ4fyK+EXqnR0kpyaX3qh+lS fdwFzsvZhmKZP1tsMMv/XNIj/U+TgTvf/Fb+wUaa8m0m+gBdIb/4AVL+2xbGiphb0YV0O5 mnDCCePW+gluc50cfEzlG5aGdFFOfdVtJ1hO2hBtbXpH//692fpp9PkEwxSsjtxIUM77GX u74wd9lJC2qGKVpNclBMvt4Afs+Fc4+kY5GiiaqwGk2PWu7fTkKl3DBkeSvroA== To: ~johnnyrichard/olang-devel@lists.sr.ht Cc: Carlos Maniero Subject: [PATCH olang v2] arena: optimization: make arena 8 bits aligned Date: Wed, 21 Feb 2024 12:09:11 -0300 Message-Id: <20240221150911.3670778-1-carlos@maniero.me> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-CM-Envelope: MS4xfI9bAX7IAKHLE3py/dW9a6QDc6HfwOX1gw+41NTRp1+Uz2nF1HyhqNxRhcNJVPg7dFkZH2MLpsJe6PPEBEenVEIxflqucN0L2kBU0QtMJWxzmLnA1Cx7 hEWTDwosocmuVOS3kFOpg1IKT3W1ilSxZH/+RSbhd0oknBBNhk7IncQ9gxp1yUJLA/TIlN6efGspU9sT8zzKc6DqdfNsKvlJOzANAI3/vIF6TDUvJXsyTaWh X-CM-Analysis: v=2.4 cv=EuXUrzcA c=1 sm=1 tr=0 ts=65d6121e a=5+VMC1FZ3J4mVPAKpPmAqg==:117 a=5+VMC1FZ3J4mVPAKpPmAqg==:17 a=MKtGQD3n3ToA:10 a=1oJP67jkp3AA:10 a=BXDaF_L80NYA:10 a=eb9qOAMCG0MG6iJXngkA:9 X-AuthUser: carlos@maniero.me X-TUID: +IJMFuQ9cLaB 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 --- 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 #include +#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