# Adaptive Re-sortable List (ARL) This library allows Netdata to read a series of `name - value` pairs in the **fastest possible way**. ARLs are used all over Netdata, as they are the most CPU utilization efficient way to process `/proc` files. They are used to process both vertical (csv like) and horizontal (one pair per line) `name - value` pairs. ## How ARL works It maintains a linked list of all `NAME` (keywords), sorted in the order found in the data source. The linked list is kept sorted at all times - the data source may change at any time, the linked list will adapt at the next iteration. ### Initialization During initialization (just once), the caller: - calls `arl_create()` to create the ARL - calls `arl_expect()` multiple times to register the expected keywords The library will call the `processor()` function (given to `arl_create()`), for each expected keyword found. The default `processor()` expects `dst` to be an `unsigned long long *`. Each `name` keyword may have a different `processor()` (by calling `arl_expect_custom()` instead of `arl_expect()`). ### Data collection iterations For each iteration through the data source, the caller: - calls `arl_begin()` to initiate a data collection iteration. This is to be called just ONCE every time the source is re-evaluated. - calls `arl_check()` for each entry read from the file. ### Cleanup When the caller exits: - calls `arl_free()` to destroy this and free all memory. ### Performance ARL maintains a list of `name` keywords found in the data source (even the ones that are not useful for data collection). If the data source maintains the same order on the `name-value` pairs, for each each call to `arl_check()` only an `strcmp()` is executed to verify the expected order has not changed, a counter is incremented and a pointer is changed. So, if the data source has 100 `name-value` pairs, and their order remains constant over time, 100 successful `strcmp()` are executed. In the unlikely event that an iteration sees the data source with a different order, for each out-of-order keyword, a full search of the remaining keywords is made. But this search uses 32bit hashes, not string comparisons, so it should also be fast. When all expectations are satisfied (even in the middle of an iteration), the call to `arl_check()` will return 1, to signal the caller to stop the loop, saving valuable CPU resources for the rest of the data source. In the following test we used alternative methods to process, **1M times**, a data source like `/proc/meminfo`, already tokenized, in memory, to extract the same number of expected metrics: |test|code|string comparison|number parsing|duration| |:--:|:--:|:---------------:|:------------:|:------:| |1|if-else-if-else-if|`strcmp()`|`strtoull()`|4630.337 ms| |2|nested loops|inline `simple_hash()` and `strcmp()`|`strtoull()`|1597.481 ms| |3|nested loops|inline `simple_hash()` and `strcmp()`|`str2ull()`|923.523 ms| |4|if-else-if-else-if|inline `simple_hash()` and `strcmp()`|`strtoull()`|854.574 ms| |5|if-else-if-else-if|statement expression `simple_hash()` and `strcmp()`|`strtoull()`|912.013 ms| |6|if-continue|inline `simple_hash()` and `strcmp()`|`strtoull()`|842.279 ms| |7|if-else-if-else-if|inline `simple_hash()` and `strcmp()`|`str2ull()`|602.837 ms| |8|ARL|ARL|`strtoull()`|350.360 ms| |9|ARL|ARL|`str2ull()`|157.237 ms| Compared to unoptimized code (test No 1: 4.6sec): - before ARL Netdata was using test No **7** with hashing and a custom `str2ull()` to achieve 602ms. - the current ARL implementation is test No **9** that needs only 157ms (29 times faster vs unoptimized code, about 4 times faster vs optimized code). [Check the source code of this test](https://raw.githubusercontent.com/netdata/netdata/master/tests/profile/benchmark-value-pairs.c). ## Limitations Do not use ARL if the a name/keyword may appear more than once in the source data.