NVIDIA / NVIDIA/cudf

[FEA] Story - Improve performance with long strings

Open
#13,048 7 comments 0 reactions 1 assignee Claimed by @davidwendt View on GitHub
2 - In Progress libcudf Performance strings
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

Many [strings APIs in libcudf](https://docs.rapids.ai/api/libcudf/stable/group__strings__apis.html) use thread-per-string parallelism in their implementation. This approach works great for processing smaller strings of relatively consistent length. However, for long strings (roughly 256 bytes and above) the performance of thread-per-string algorithms begins to degrade. Some strings APIs are compatible with data-parallel algorithms and can be refactored to improve performance for long strings, while other strings APIs are difficult to refactor with data-parallel algorithms.

Let's use this issue to track the progression:
βœ… - this API works well with long strings
🟒 - we think this API will be straightforward to refactor
🟑 - we have some ideas on how to refactor this API, and we'll need to experiment
πŸ”΄ - we think this will be very difficult to refactor!
βšͺ - long string support is not a priority for this API

|Module|Function|Status|Notes|
|---|---|---|---|
| [Case](https://docs.rapids.ai/api/libcudf/nightly/group__strings__case.html) | capitalize
title
is_title
to_lower
to_upper
swapcase | 🟑
🟑
🟑
βœ…#13142
βœ…#13142
βœ…#13142 | |
| [Character Types](https://docs.rapids.ai/api/libcudf/nightly/group__strings__types.html) | all_characters_of_type
filter_characters_of_type | βœ…#13259
πŸ”΄ | |
| [Combining](https://docs.rapids.ai/api/libcudf/nightly/group__strings__combine.html) | join_strings
concatenate
join_list_elements | βœ…#13283
🟑
πŸ”΄ | |
| [Searching](https://docs.rapids.ai/api/libcudf/nightly/group__strings__contains.html) | contains_re
matches_re
count_re
like
find_all | 🟑
βšͺ
πŸ”΄
🟒#13594
πŸ”΄ | |
| [Converting](https://docs.rapids.ai/api/libcudf/nightly/group__strings__convert.html) | to_XXXX
from_XXXX | βšͺ
βšͺ | these are rarely long strings|
| [Copying](https://docs.rapids.ai/api/libcudf/nightly/group__strings__copy.html) | repeat_string
repeat_strings | βœ…
βœ… | One [overload](https://docs.rapids.ai/api/libcudf/nightly/group__strings__copy.html#ga160c075327cb4fb081db19884dba294c) is an exception |
| [Slicing](https://docs.rapids.ai/api/libcudf/nightly/group__strings__slice.html) | slice_strings | βœ…#13057 | One [overload](https://docs.rapids.ai/api/libcudf/nightly/group__strings__slice.html#ga2bc738cebebcf6d1331d6e9d13d4cd28) allows for skipping characters.
Long string support is not a priority for
`step > 1 or step < 0` |
| [Finding](https://docs.rapids.ai/api/libcudf/nightly/group__strings__find.html) | find
rfind
contains
starts_with
ends_with
find_multiple | βœ…#13226
βœ…#13226
βœ…#10739
βšͺ
βšͺ
🟒 | |
| [Modifying](https://docs.rapids.ai/api/libcudf/nightly/group__strings__modify.html) | pad
zfill
reverse
strip
translate
filter_characters
wrap | 🟑
βšͺ
🟑
βœ…
🟑
πŸ”΄
πŸ”΄ | |
| [Replacing](https://docs.rapids.ai/api/libcudf/nightly/group__strings__replace.html) | replace
replace_slice
replace_re
replace_with_backrefs | βœ…#12858
🟑
πŸ”΄
πŸ”΄ | |
| [Splitting](https://docs.rapids.ai/api/libcudf/nightly/group__strings__split.html) | partition
split
split_record
split_re
split_record_re | 🟑
βœ…#4922 #13680
βœ…#12729
πŸ”΄
πŸ”΄ | |
| other | count_characters
count_bytes| βœ…#12779
🟒 | |

Libcudf also includes [NVText](https://docs.rapids.ai/api/libcudf/stable/group__nvtext__apis.html) APIs that will benefit from improvements in performance when processing long strings. Generally long string performance is even more important for our text APIs, where each row could represent a sentence, paragraph or document.

|Module|Function|Status|Notes|
|---|---|---|---|
| [NGrams](https://docs.rapids.ai/api/libcudf/stable/group__nvtext__ngrams.html) | generate_ngrams
generate_character_ngrams
ngrams_tokenize| βšͺ
🟒
🟒#13480 | these are generally not long strings |
| [Normalizing](https://docs.rapids.ai/api/libcudf/stable/group__nvtext__normalize.html) | normalize_characters
normalize_spaces | 🟒
🟒#13480 | |
| [Stemming](https://docs.rapids.ai/api/libcudf/stable/group__nvtext__stemmer.html) | is_letter
porter_stemmer_measure | 🟒
🟒 | |
| [Edit Distance](https://docs.rapids.ai/api/libcudf/stable/group__nvtext__edit__distance.html) | edit_distance
edit_distance_matrix | βšͺ
βšͺ | these are generally not long strings |
| [Tokenizing](https://docs.rapids.ai/api/libcudf/stable/group__nvtext__tokenize.html) | byte_pair_encoding
subword_tokenize
tokenize
count_tokens
character_tokenize
detokenize | 🟑
🟑
🟒#13480
🟒#13480
🟑
🟑 | |
| [Replacing](https://docs.rapids.ai/api/libcudf/stable/group__nvtext__replace.html) | replace_tokens
filter_tokens | 🟒#13480
🟒#13480 | |
| [MinHashing](https://docs.rapids.ai/api/libcudf/nightly/group__nvtext__minhash.html) | minhash | βœ…#13333 | |

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.