From 6d51b974d10b77fd71f67c14cf5c5c769bfed78f Mon Sep 17 00:00:00 2001 From: Kevin Day Date: Sun, 4 Aug 2024 01:15:14 -0500 Subject: [PATCH] Update: Greatly reduce memory consumption by implementing simple low allocation step. Historically the step was always 3. I found, over time, that increasing the step greatly to something like 128 could greatly reduce memory consumption and performance in many cases. In the situation where a large number of small objects are allocated then this number like 128 becomes highly abusive. The simple low allocation step will only allocate a single unit on the very first allocation. If the next allocation is on an array that has a size greater than one and less than four (via the tiny define), then the step size is set to four during allocation. If the next allocation is on an array that has a size greater than four and less than eight (via the small define), then the step size is set to eight during allocation. If the next allocation is on an array that has a size greater than eight and less than sixty-four (via the large define), then the step size is set to sixty-four during allocation. In all cases, if the request step is less than the calculated step, then the requested step is used. For example, if the requested step is twelve, then after eight is allocation, then the next generated step size is twelve rather than sixty-four. Using some test files, shows the following reduction: - Old: ~8GB of RAM -> New: ~200MB of RAM. - Old: ~500MB of RAM -> New: ~20MB of RAM. Update the unit tests accordingly and fix any problems exposed. --- build/stand_alone/byte_dump.config.h | 1 + build/stand_alone/example.config.h | 1 + build/stand_alone/fake.config.h | 1 + build/stand_alone/firewall.config.h | 1 + build/stand_alone/utf8.config.h | 1 + .../tests/unit/c/test-iki-datass_append.c | 4 +- level_0/f_memory/c/memory/array.c | 2 +- level_0/f_memory/c/memory/common.h | 48 +++++++++++++++++++ .../tests/unit/c/test-memory-array_increase.c | 47 ++++++++++++++++++ .../tests/unit/c/test-memory-array_increase.h | 11 +++++ level_0/f_memory/tests/unit/c/test-memory.c | 5 ++ level_1/fl_fss/c/fss/basic.c | 2 +- .../fl_fss/tests/unit/c/help-fss-payload.c | 2 +- 13 files changed, 121 insertions(+), 5 deletions(-) diff --git a/build/stand_alone/byte_dump.config.h b/build/stand_alone/byte_dump.config.h index 08e71ee63..6f6eb942b 100644 --- a/build/stand_alone/byte_dump.config.h +++ b/build/stand_alone/byte_dump.config.h @@ -661,6 +661,7 @@ //#define _di_f_memory_default_d_ //#define _di_f_memory_delete_ #define _di_f_memory_destroy_ +//#define _di_f_memory_increase_step_d_ #define _di_f_memory_new_ #define _di_f_memory_new_aligned_ //#define _di_f_memory_resize_ diff --git a/build/stand_alone/example.config.h b/build/stand_alone/example.config.h index bb6dc3997..dc0679e02 100644 --- a/build/stand_alone/example.config.h +++ b/build/stand_alone/example.config.h @@ -586,6 +586,7 @@ //#define _di_f_memory_default_d_ //#define _di_f_memory_delete_ #define _di_f_memory_destroy_ +//#define _di_f_memory_increase_step_d_ #define _di_f_memory_new_ #define _di_f_memory_new_aligned_ //#define _di_f_memory_resize_ diff --git a/build/stand_alone/fake.config.h b/build/stand_alone/fake.config.h index 9fff1e2ce..4e966123f 100644 --- a/build/stand_alone/fake.config.h +++ b/build/stand_alone/fake.config.h @@ -1041,6 +1041,7 @@ //#define _di_f_memory_default_d_ //#define _di_f_memory_delete_ #define _di_f_memory_destroy_ +//#define _di_f_memory_increase_step_d_ #define _di_f_memory_new_ #define _di_f_memory_new_aligned_ //#define _di_f_memory_resize_ diff --git a/build/stand_alone/firewall.config.h b/build/stand_alone/firewall.config.h index f4427d3d9..e05db3859 100644 --- a/build/stand_alone/firewall.config.h +++ b/build/stand_alone/firewall.config.h @@ -1062,6 +1062,7 @@ //#define _di_f_memory_default_d_ //#define _di_f_memory_delete_ #define _di_f_memory_destroy_ +//#define _di_f_memory_increase_step_d_ #define _di_f_memory_new_ #define _di_f_memory_new_aligned_ //#define _di_f_memory_resize_ diff --git a/build/stand_alone/utf8.config.h b/build/stand_alone/utf8.config.h index 590dde48c..8c820266f 100644 --- a/build/stand_alone/utf8.config.h +++ b/build/stand_alone/utf8.config.h @@ -661,6 +661,7 @@ //#define _di_f_memory_default_d_ //#define _di_f_memory_delete_ #define _di_f_memory_destroy_ +//#define _di_f_memory_increase_step_d_ #define _di_f_memory_new_ #define _di_f_memory_new_aligned_ //#define _di_f_memory_resize_ diff --git a/level_0/f_iki/tests/unit/c/test-iki-datass_append.c b/level_0/f_iki/tests/unit/c/test-iki-datass_append.c index b912e3e67..c15afabf4 100644 --- a/level_0/f_iki/tests/unit/c/test-iki-datass_append.c +++ b/level_0/f_iki/tests/unit/c/test-iki-datass_append.c @@ -76,7 +76,7 @@ void test__f_iki_datass_append__works(void **state) { assert_int_equal(destination.used, 1); assert_int_equal(destination.array[0].used, source.used); - for (f_number_unsigned_t j = 0; j < length_outer; ++j) { + for (f_number_unsigned_t j = 0; j < destination.used; ++j) { assert_int_equal(destination.array[0].array[j].content.used, source.array[j].content.used); assert_int_equal(destination.array[0].array[j].delimits.used, source.array[j].delimits.used); @@ -107,7 +107,7 @@ void test__f_iki_datass_append__works(void **state) { free((void *) source.array[i].vocabulary.array); } // for - for (f_number_unsigned_t j = 0; j < length_outer; ++j) { + for (f_number_unsigned_t j = 0; j < destination.used; ++j) { for (f_number_unsigned_t i = 0; i < destination.array[j].used; ++i) { diff --git a/level_0/f_memory/c/memory/array.c b/level_0/f_memory/c/memory/array.c index d51383539..66423d288 100644 --- a/level_0/f_memory/c/memory/array.c +++ b/level_0/f_memory/c/memory/array.c @@ -127,7 +127,7 @@ extern "C" { #endif // _di_level_0_parameter_checking_ if (step && *used + 1 > *size) { - const f_number_unsigned_t length = *used + step; + const f_number_unsigned_t length = *used + macro_f_memory_increase_step_4(step, (*size)); if (length > F_number_t_size_unsigned_d || length < *used) return F_status_set_error(F_array_too_large); diff --git a/level_0/f_memory/c/memory/common.h b/level_0/f_memory/c/memory/common.h index 5e2846385..994c296cb 100644 --- a/level_0/f_memory/c/memory/common.h +++ b/level_0/f_memory/c/memory/common.h @@ -40,8 +40,56 @@ extern "C" { #ifndef _di_f_memory_default_d_ #define F_memory_default_allocation_large_d 64 #define F_memory_default_allocation_small_d 8 + #define F_memory_default_allocation_tiny_d 4 #endif // _di_f_memory_default_d_ +/** + * Helper macros for conditionally determining how much memory to allocate for a given step. + * + * For each macro: + * - step: Represents the amount to increase past the helper amount. + * - size: Represents the amount already allocated. + * + * macro_f_memory_increase_*: + * - 1: If size is 0, then allocate 1, otherwise allocate step. + * - 2: As step 1, plus if size is 1, then allocate tiny, otherwise allocate step. + * - 3: As step 2, plus if size is less than small, then allocate small, otherwise allocate step. + * - 4: As step 3, plus if size is less than large, then allocate large, otherwise allocate step. + */ +#ifndef _di_f_memory_increase_step_d_ + #define macro_f_memory_increase_step_1(step, size) (size \ + ? step \ + : 1 \ + ) + + #define macro_f_memory_increase_step_2(step, size) (size \ + ? size == 1 \ + ? step < F_memory_default_allocation_tiny_d ? step : F_memory_default_allocation_tiny_d \ + : step \ + : 1 \ + ) + + #define macro_f_memory_increase_step_3(step, size) (size \ + ? size == 1 \ + ? step < F_memory_default_allocation_tiny_d ? step : F_memory_default_allocation_tiny_d \ + : size < F_memory_default_allocation_small_d \ + ? step < F_memory_default_allocation_small_d ? step : F_memory_default_allocation_small_d \ + : step \ + : 1 \ + ) + + #define macro_f_memory_increase_step_4(step, size) (size \ + ? size == 1 \ + ? step < F_memory_default_allocation_tiny_d ? step : F_memory_default_allocation_tiny_d \ + : size < F_memory_default_allocation_small_d \ + ? step < F_memory_default_allocation_small_d ? step : F_memory_default_allocation_small_d \ + : size < F_memory_default_allocation_large_d \ + ? step < F_memory_default_allocation_large_d ? step : F_memory_default_allocation_large_d \ + : step \ + : 1 \ + ) +#endif // _di_f_memory_increase_step_d_ + #ifdef __cplusplus } // extern "C" #endif diff --git a/level_0/f_memory/tests/unit/c/test-memory-array_increase.c b/level_0/f_memory/tests/unit/c/test-memory-array_increase.c index 2210fa02a..5543ed019 100644 --- a/level_0/f_memory/tests/unit/c/test-memory-array_increase.c +++ b/level_0/f_memory/tests/unit/c/test-memory-array_increase.c @@ -118,6 +118,53 @@ void test__f_memory_array_increase__works(void **state) { free((void *) data.array); } +void test__f_memory_array_increase__works_for_step_increase(void **state) { + + const int huge = F_memory_default_allocation_large_d + 5; + const f_number_unsigned_t plus_1_tiny = 1 + F_memory_default_allocation_tiny_d; + const f_number_unsigned_t plus_1_tiny_small = plus_1_tiny + F_memory_default_allocation_small_d; + const f_number_unsigned_t plus_1_tiny_small_large = plus_1_tiny_small + F_memory_default_allocation_large_d; + + test_memory_array_t data = test_memory_array_t_initialize; + f_number_unsigned_t previous = 0; + + const f_number_unsigned_t lengths[] = { + huge, + F_memory_default_allocation_large_d, + F_memory_default_allocation_small_d, + F_memory_default_allocation_tiny_d, + 1, + }; + + const f_number_unsigned_t sets[][5] = { + { 1, plus_1_tiny, plus_1_tiny_small, plus_1_tiny_small_large, plus_1_tiny_small_large + lengths[0] }, + { 1, plus_1_tiny, plus_1_tiny_small, plus_1_tiny_small_large, plus_1_tiny_small_large + lengths[1] }, + { 1, plus_1_tiny, plus_1_tiny_small, plus_1_tiny_small + lengths[2], plus_1_tiny_small + lengths[2] * 2 }, + { 1, plus_1_tiny, plus_1_tiny + lengths[3], plus_1_tiny + lengths[3] * 2, plus_1_tiny + lengths[3] * 3 }, + { 1, 2, 3, 4, 5 }, + }; + + for (uint8_t i = 0; i < 5; ++i) { + + for (uint8_t j = 0; j < 5; ++j) { + + const f_status_t status = f_memory_array_increase(lengths[i], sizeof(int), (void **) &data.array, &data.used, &data.size); + + assert_int_equal(status, F_okay); + assert_int_equal(data.used, previous); + assert_int_equal(data.size, sets[i][j]); + + previous = data.used = data.size; + } // for + + free((void *) data.array); + data.array = 0; + data.used = 0; + data.size = 0; + previous = 0; + } // for +} + #ifdef __cplusplus } // extern "C" #endif diff --git a/level_0/f_memory/tests/unit/c/test-memory-array_increase.h b/level_0/f_memory/tests/unit/c/test-memory-array_increase.h index 04635e81b..d7b7a9dea 100644 --- a/level_0/f_memory/tests/unit/c/test-memory-array_increase.h +++ b/level_0/f_memory/tests/unit/c/test-memory-array_increase.h @@ -38,4 +38,15 @@ extern void test__f_memory_array_increase__returns_data_not(void **state); */ extern void test__f_memory_array_increase__works(void **state); +/** + * Test that the function works for step increase. + * + * This test expects the macro_f_memory_increase_step_4 to be used by f_memory_array_increase(). + * This test expects the F_memory_default_allocation_*_d to be used. + * This test expects the first allocation step to be of size 1. + * + * @see f_memory_array_increase() + */ +extern void test__f_memory_array_increase__works_for_step_increase(void **state); + #endif // _TEST__F_memory__array_increase diff --git a/level_0/f_memory/tests/unit/c/test-memory.c b/level_0/f_memory/tests/unit/c/test-memory.c index ccf5cfc95..7e7acc3a0 100644 --- a/level_0/f_memory/tests/unit/c/test-memory.c +++ b/level_0/f_memory/tests/unit/c/test-memory.c @@ -29,6 +29,11 @@ int main(void) { cmocka_unit_test(test__f_memory_destroy__frees_memory), cmocka_unit_test(test__f_memory_destroy__frees_resized_memory), + cmocka_unit_test(test__f_memory_array_increase__works), + cmocka_unit_test(test__f_memory_array_increase__works_for_step_increase), + + cmocka_unit_test(test__f_memory_array_increase_by__works), + cmocka_unit_test(test__f_memory_new__works), cmocka_unit_test(test__f_memory_new_aligned__works), diff --git a/level_1/fl_fss/c/fss/basic.c b/level_1/fl_fss/c/fss/basic.c index a8e2c45ea..5d6e287cf 100644 --- a/level_1/fl_fss/c/fss/basic.c +++ b/level_1/fl_fss/c/fss/basic.c @@ -58,7 +58,7 @@ extern "C" { if (F_status_is_error(state->status)) return; - state->status = f_memory_array_increase(found->size ? found->size == 1 ? 4 : state->step_small : 1, sizeof(f_range_t), (void **) &found->array, &found->used, &found->size); + state->status = f_memory_array_increase(state->step_small, sizeof(f_range_t), (void **) &found->array, &found->used, &found->size); if (F_status_is_error(state->status)) return; if (range->start > begin) { diff --git a/level_1/fl_fss/tests/unit/c/help-fss-payload.c b/level_1/fl_fss/tests/unit/c/help-fss-payload.c index 9f2f64856..36d663325 100644 --- a/level_1/fl_fss/tests/unit/c/help-fss-payload.c +++ b/level_1/fl_fss/tests/unit/c/help-fss-payload.c @@ -40,7 +40,7 @@ void help_payload__test(const f_string_t context_variables, const f_string_t con if (help__read_line_object(file_variables, &object)) break; if (help__read_line_contents__single(file_variables, &contents, F_true)) break; - state.status = f_memory_array_increase(state.step_small, sizeof(f_abstruse_map_t), (void **) &headers.array, &headers.used, &headers.size); + state.status = f_memory_array_increase_by(contents.used + state.step_small, sizeof(f_abstruse_map_t), (void **) &headers.array, &headers.used, &headers.size); assert_true(F_status_is_error_not(state.status)); load_contents(object, contents, &headers, &state, extra); -- 2.47.3