diff options
Diffstat (limited to '')
| -rw-r--r-- | libnetdata/storage_number/Makefile.am | 12 | ||||
| -rw-r--r-- | libnetdata/storage_number/README.md | 17 | ||||
| -rw-r--r-- | libnetdata/storage_number/storage_number.c | 252 | ||||
| -rw-r--r-- | libnetdata/storage_number/storage_number.h | 94 | ||||
| -rw-r--r-- | libnetdata/storage_number/tests/Makefile.am | 4 | ||||
| -rw-r--r-- | libnetdata/storage_number/tests/test_storage_number.c | 52 |
6 files changed, 431 insertions, 0 deletions
diff --git a/libnetdata/storage_number/Makefile.am b/libnetdata/storage_number/Makefile.am new file mode 100644 index 0000000..c5f8450 --- /dev/null +++ b/libnetdata/storage_number/Makefile.am @@ -0,0 +1,12 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in + +SUBDIRS = \ + tests \ + $(NULL) + +dist_noinst_DATA = \ + README.md \ + $(NULL) diff --git a/libnetdata/storage_number/README.md b/libnetdata/storage_number/README.md new file mode 100644 index 0000000..295b3d6 --- /dev/null +++ b/libnetdata/storage_number/README.md @@ -0,0 +1,17 @@ +<!-- +title: "Netdata storage number" +custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/storage_number/README.md +--> + +# Netdata storage number + +Although `netdata` does all its calculations using `long double`, it stores all values using +a **custom-made 32-bit number**. + +This custom-made number can store in 29 bits values from `-167772150000000.0` to `167772150000000.0` +with a precision of 0.00001 (yes, it's a floating point number, meaning that higher integer values +have less decimal precision) and 3 bits for flags. + +This provides an extremely optimized memory footprint with just 0.0001% max accuracy loss. + +[](<>) diff --git a/libnetdata/storage_number/storage_number.c b/libnetdata/storage_number/storage_number.c new file mode 100644 index 0000000..8ef1353 --- /dev/null +++ b/libnetdata/storage_number/storage_number.c @@ -0,0 +1,252 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "../libnetdata.h" + +storage_number pack_storage_number(calculated_number value, uint32_t flags) { + // bit 32 = sign 0:positive, 1:negative + // bit 31 = 0:divide, 1:multiply + // bit 30, 29, 28 = (multiplier or divider) 0-7 (8 total) + // bit 27 SN_EXISTS_100 + // bit 26 SN_EXISTS_RESET + // bit 25 SN_EXISTS + // bit 24 to bit 1 = the value + + storage_number r = get_storage_number_flags(flags); + if(!value) return r; + + int m = 0; + calculated_number n = value, factor = 10; + + // if the value is negative + // add the sign bit and make it positive + if(n < 0) { + r += (1 << 31); // the sign bit 32 + n = -n; + } + + if(n / 10000000.0 > 0x00ffffff) { + factor = 100; + r |= SN_EXISTS_100; + } + + // make its integer part fit in 0x00ffffff + // by dividing it by 10 up to 7 times + // and increasing the multiplier + while(m < 7 && n > (calculated_number)0x00ffffff) { + n /= factor; + m++; + } + + if(m) { + // the value was too big and we divided it + // so we add a multiplier to unpack it + r += (1 << 30) + (m << 27); // the multiplier m + + if(n > (calculated_number)0x00ffffff) { + #ifdef NETDATA_INTERNAL_CHECKS + error("Number " CALCULATED_NUMBER_FORMAT " is too big.", value); + #endif + r += 0x00ffffff; + return r; + } + } + else { + // 0x0019999e is the number that can be multiplied + // by 10 to give 0x00ffffff + // while the value is below 0x0019999e we can + // multiply it by 10, up to 7 times, increasing + // the multiplier + while(m < 7 && n < (calculated_number)0x0019999e) { + n *= 10; + m++; + } + + if (unlikely(n > (calculated_number) (0x00ffffff))) { + n /= 10; + m--; + } + // the value was small enough and we multiplied it + // so we add a divider to unpack it + r += (0 << 30) + (m << 27); // the divider m + } + +#ifdef STORAGE_WITH_MATH + // without this there are rounding problems + // example: 0.9 becomes 0.89 + r += lrint((double) n); +#else + r += (storage_number)n; +#endif + + return r; +} + +calculated_number unpack_storage_number(storage_number value) { + if(!value) return 0; + + int sign = 0, exp = 0; + int factor = 10; + + // bit 32 = 0:positive, 1:negative + if(unlikely(value & (1 << 31))) + sign = 1; + + // bit 31 = 0:divide, 1:multiply + if(unlikely(value & (1 << 30))) + exp = 1; + + // bit 27 SN_EXISTS_100 + if(unlikely(value & (1 << 26))) + factor = 100; + + // bit 26 SN_EXISTS_RESET + // bit 25 SN_EXISTS + + // bit 30, 29, 28 = (multiplier or divider) 0-7 (8 total) + int mul = (value & ((1<<29)|(1<<28)|(1<<27))) >> 27; + + // bit 24 to bit 1 = the value, so remove all other bits + value ^= value & ((1<<31)|(1<<30)|(1<<29)|(1<<28)|(1<<27)|(1<<26)|(1<<25)|(1<<24)); + + calculated_number n = value; + + // fprintf(stderr, "UNPACK: %08X, sign = %d, exp = %d, mul = %d, factor = %d, n = " CALCULATED_NUMBER_FORMAT "\n", value, sign, exp, mul, factor, n); + + if(exp) { + for(; mul; mul--) + n *= factor; + } + else { + for( ; mul ; mul--) + n /= 10; + } + + if(sign) n = -n; + return n; +} + +/* +int print_calculated_number(char *str, calculated_number value) +{ + char *wstr = str; + + int sign = (value < 0) ? 1 : 0; + if(sign) value = -value; + +#ifdef STORAGE_WITH_MATH + // without llrintl() there are rounding problems + // for example 0.9 becomes 0.89 + unsigned long long uvalue = (unsigned long long int) llrintl(value * (calculated_number)100000); +#else + unsigned long long uvalue = value * (calculated_number)100000; +#endif + + wstr = print_number_llu_r_smart(str, uvalue); + + // make sure we have 6 bytes at least + while((wstr - str) < 6) *wstr++ = '0'; + + // put the sign back + if(sign) *wstr++ = '-'; + + // reverse it + char *begin = str, *end = --wstr, aux; + while (end > begin) aux = *end, *end-- = *begin, *begin++ = aux; + // wstr--; + // strreverse(str, wstr); + + // remove trailing zeros + int decimal = 5; + while(decimal > 0 && *wstr == '0') { + *wstr-- = '\0'; + decimal--; + } + + // terminate it, one position to the right + // to let space for a dot + wstr[2] = '\0'; + + // make space for the dot + int i; + for(i = 0; i < decimal ;i++) { + wstr[1] = wstr[0]; + wstr--; + } + + // put the dot + if(wstr[2] == '\0') { wstr[1] = '\0'; decimal--; } + else wstr[1] = '.'; + + // return the buffer length + return (int) ((wstr - str) + 2 + decimal ); +} +*/ + +int print_calculated_number(char *str, calculated_number value) { + // info("printing number " CALCULATED_NUMBER_FORMAT, value); + char integral_str[50], fractional_str[50]; + + char *wstr = str; + + if(unlikely(value < 0)) { + *wstr++ = '-'; + value = -value; + } + + calculated_number integral, fractional; + +#ifdef STORAGE_WITH_MATH + fractional = calculated_number_modf(value, &integral) * 10000000.0; +#else + fractional = ((unsigned long long)(value * 10000000ULL) % 10000000ULL); +#endif + + unsigned long long integral_int = (unsigned long long)integral; + unsigned long long fractional_int = (unsigned long long)calculated_number_llrint(fractional); + if(unlikely(fractional_int >= 10000000)) { + integral_int += 1; + fractional_int -= 10000000; + } + + // info("integral " CALCULATED_NUMBER_FORMAT " (%llu), fractional " CALCULATED_NUMBER_FORMAT " (%llu)", integral, integral_int, fractional, fractional_int); + + char *istre; + if(unlikely(integral_int == 0)) { + integral_str[0] = '0'; + istre = &integral_str[1]; + } + else + // convert the integral part to string (reversed) + istre = print_number_llu_r_smart(integral_str, integral_int); + + // copy reversed the integral string + istre--; + while( istre >= integral_str ) *wstr++ = *istre--; + + if(likely(fractional_int != 0)) { + // add a dot + *wstr++ = '.'; + + // convert the fractional part to string (reversed) + char *fstre = print_number_llu_r_smart(fractional_str, fractional_int); + + // prepend zeros to reach 7 digits length + int decimal = 7; + int len = (int)(fstre - fractional_str); + while(len < decimal) { + *wstr++ = '0'; + len++; + } + + char *begin = fractional_str; + while(begin < fstre && *begin == '0') begin++; + + // copy reversed the fractional string + fstre--; + while( fstre >= begin ) *wstr++ = *fstre--; + } + + *wstr = '\0'; + // info("printed number '%s'", str); + return (int)(wstr - str); +} diff --git a/libnetdata/storage_number/storage_number.h b/libnetdata/storage_number/storage_number.h new file mode 100644 index 0000000..28b7f26 --- /dev/null +++ b/libnetdata/storage_number/storage_number.h @@ -0,0 +1,94 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef NETDATA_STORAGE_NUMBER_H +#define NETDATA_STORAGE_NUMBER_H 1 + +#include "../libnetdata.h" + +#ifdef NETDATA_WITHOUT_LONG_DOUBLE + +#define powl pow +#define modfl modf +#define llrintl llrint +#define roundl round +#define sqrtl sqrt +#define copysignl copysign +#define strtold strtod + +typedef double calculated_number; +#define CALCULATED_NUMBER_FORMAT "%0.7f" +#define CALCULATED_NUMBER_FORMAT_ZERO "%0.0f" +#define CALCULATED_NUMBER_FORMAT_AUTO "%f" + +#define LONG_DOUBLE_MODIFIER "f" +typedef double LONG_DOUBLE; + +#else // NETDATA_WITHOUT_LONG_DOUBLE + +typedef long double calculated_number; +#define CALCULATED_NUMBER_FORMAT "%0.7Lf" +#define CALCULATED_NUMBER_FORMAT_ZERO "%0.0Lf" +#define CALCULATED_NUMBER_FORMAT_AUTO "%Lf" + +#define LONG_DOUBLE_MODIFIER "Lf" +typedef long double LONG_DOUBLE; + +#endif // NETDATA_WITHOUT_LONG_DOUBLE + +//typedef long long calculated_number; +//#define CALCULATED_NUMBER_FORMAT "%lld" + +typedef long long collected_number; +#define COLLECTED_NUMBER_FORMAT "%lld" + +/* +typedef long double collected_number; +#define COLLECTED_NUMBER_FORMAT "%0.7Lf" +*/ + +#define calculated_number_modf(x, y) modfl(x, y) +#define calculated_number_llrint(x) llrintl(x) +#define calculated_number_round(x) roundl(x) +#define calculated_number_fabs(x) fabsl(x) +#define calculated_number_pow(x, y) powl(x, y) +#define calculated_number_epsilon (calculated_number)0.0000001 + +#define calculated_number_equal(a, b) (calculated_number_fabs((a) - (b)) < calculated_number_epsilon) + +#define calculated_number_isnumber(a) (!(fpclassify(a) & (FP_NAN|FP_INFINITE))) + +typedef uint32_t storage_number; +#define STORAGE_NUMBER_FORMAT "%u" + +#define SN_EXISTS (1 << 24) // the value exists +#define SN_EXISTS_RESET (1 << 25) // the value has been overflown +#define SN_EXISTS_100 (1 << 26) // very large value (multipler is 100 instead of 10) + +// extract the flags +#define get_storage_number_flags(value) ((((storage_number)(value)) & (1 << 24)) | (((storage_number)(value)) & (1 << 25)) | (((storage_number)(value)) & (1 << 26))) +#define SN_EMPTY_SLOT 0x00000000 + +// checks +#define does_storage_number_exist(value) ((get_storage_number_flags(value) != 0)?1:0) +#define did_storage_number_reset(value) ((get_storage_number_flags(value) == SN_EXISTS_RESET)?1:0) + +storage_number pack_storage_number(calculated_number value, uint32_t flags); +calculated_number unpack_storage_number(storage_number value); + +int print_calculated_number(char *str, calculated_number value); + +// sign div/mul <--- multiplier / divider ---> 10/100 RESET EXISTS VALUE +#define STORAGE_NUMBER_POSITIVE_MAX_RAW (storage_number)( (0 << 31) | (1 << 30) | (1 << 29) | (1 << 28) | (1<<27) | (1 << 26) | (0 << 25) | (1 << 24) | 0x00ffffff ) +#define STORAGE_NUMBER_POSITIVE_MIN_RAW (storage_number)( (0 << 31) | (0 << 30) | (1 << 29) | (1 << 28) | (1<<27) | (0 << 26) | (0 << 25) | (1 << 24) | 0x00000001 ) +#define STORAGE_NUMBER_NEGATIVE_MAX_RAW (storage_number)( (1 << 31) | (0 << 30) | (1 << 29) | (1 << 28) | (1<<27) | (0 << 26) | (0 << 25) | (1 << 24) | 0x00000001 ) +#define STORAGE_NUMBER_NEGATIVE_MIN_RAW (storage_number)( (1 << 31) | (1 << 30) | (1 << 29) | (1 << 28) | (1<<27) | (1 << 26) | (0 << 25) | (1 << 24) | 0x00ffffff ) + +// accepted accuracy loss +#define ACCURACY_LOSS_ACCEPTED_PERCENT 0.0001 +#define accuracy_loss(t1, t2) (((t1) == (t2) || (t1) == 0.0 || (t2) == 0.0) ? 0.0 : (100.0 - (((t1) > (t2)) ? ((t2) * 100.0 / (t1) ) : ((t1) * 100.0 / (t2))))) + +// Maximum acceptable rate of increase for counters. With a rate of 10% netdata can safely detect overflows with a +// period of at least every other 10 samples. +#define MAX_INCREMENTAL_PERCENT_RATE 10 + +#endif /* NETDATA_STORAGE_NUMBER_H */ diff --git a/libnetdata/storage_number/tests/Makefile.am b/libnetdata/storage_number/tests/Makefile.am new file mode 100644 index 0000000..babdcf0 --- /dev/null +++ b/libnetdata/storage_number/tests/Makefile.am @@ -0,0 +1,4 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in diff --git a/libnetdata/storage_number/tests/test_storage_number.c b/libnetdata/storage_number/tests/test_storage_number.c new file mode 100644 index 0000000..0e13208 --- /dev/null +++ b/libnetdata/storage_number/tests/test_storage_number.c @@ -0,0 +1,52 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "../../libnetdata.h" +#include "../../required_dummies.h" +#include <setjmp.h> +#include <cmocka.h> + +static void test_number_pinting(void **state) +{ + (void)state; + + char value[50]; + + print_calculated_number(value, 0); + assert_string_equal(value, "0"); + + print_calculated_number(value, 0.0000001); + assert_string_equal(value, "0.0000001"); + + print_calculated_number(value, 0.00000009); + assert_string_equal(value, "0.0000001"); + + print_calculated_number(value, 0.000000001); + assert_string_equal(value, "0"); + + print_calculated_number(value, 99.99999999999999999); + assert_string_equal(value, "100"); + + print_calculated_number(value, -99.99999999999999999); + assert_string_equal(value, "-100"); + + print_calculated_number(value, 123.4567890123456789); + assert_string_equal(value, "123.456789"); + + print_calculated_number(value, 9999.9999999); + assert_string_equal(value, "9999.9999999"); + + print_calculated_number(value, -9999.9999999); + assert_string_equal(value, "-9999.9999999"); + + print_calculated_number(value, unpack_storage_number(pack_storage_number(16.777218L, SN_EXISTS))); + assert_string_equal(value, "16.77722"); +} + +int main(void) +{ + const struct CMUnitTest tests[] = { + cmocka_unit_test(test_number_pinting) + }; + + return cmocka_run_group_tests_name("storage_number", tests, NULL, NULL); +} |