Skip to content

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.

Limitations

Do not use ARL if the a name/keyword may appear more than once in the
source data.