h2oai / h2oai/datatable

Improve NA-handling algorithm

Open
#1,023 0 comments 0 reactions 0 assignees View on GitHub
fread low priority performance
Dominant language
C++
Stars
1.9k
Forks
164
Avg merge
7h 31m
Merged PRs (30d)
1

Description

This issue outlines performance problems with current handling of NA strings, and potential ways of addressing them.

First, it must be recognized that `fread` was optimized for the case when `na_strings` list is actually absent. When the list is present, and potentially long, the performance degrades. Especially if the list contains "number-like" entries (e.g. `-999`), then "fast" parsing branch is skipped altogether. Current implementation of NA parsing is based on the following function:
```C++
const char* FreadTokenizer::end_NA_string(const char* fieldStart) {
const char* const* nastr = NAstrings;
const char* mostConsumed = fieldStart;
while (*nastr) {
const char* ch1 = fieldStart;
const char* ch2 = *nastr;
while (*ch1==*ch2 && *ch2!='\0') { ch1++; ch2++; }
if (*ch2=='\0' && ch1>mostConsumed) mostConsumed=ch1;
nastr++;
}
return mostConsumed;
}
```

Current situation can be improved upon in the following ways:
1. Re-order strings in `NAstrings` array by descending lengths, so that we could return early as soon as the first match is found (no need to check every single NA string).
2. Create a separate array of first chars in each NA string, and try to compare `*fieldStart` against them (presumably most strings are *not* NAs, so this should speed up finding the "no-match" case).
3. Instead of checking every string during parsing, postpone this to the "postprocess" stage, and then check every field in bulk. This should reduce the amount of branching. Also, it would solve some of the corner cases, such as na string containing a sep or a quote...
4. Similarly, if there are any "number-like" na strings, we could convert them into corresponding numbers and then check the corresponding numeric columns during post-processing.
5. Current detection of "number-like" strings is fragile: instead, we can use the same parsers as we already have to detect whether any na string has a risk of being matched by any of them.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.