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 + .../f_iki/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 +- level_1/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 08e71ee..6f6eb94 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 bb6dc39..dc0679e 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 9fff1e2..4e96612 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 f4427d3..e05db38 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 590dde4..8c82026 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 b912e3e..c15afab 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 d513835..66423d2 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 5e28463..994c296 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 2210fa0..5543ed0 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 04635e8..d7b7a9d 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 ccf5cfc..7e7acc3 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 a8e2c45..5d6e287 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 9f2f648..36d6633 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); -- 1.8.3.1