NVIDIA / NVIDIA/cudf

[FEA] Improve performance of strings matching in libcudf

Open
#15,611 0 comments 0 reactions 0 assignees View on GitHub
0 - Backlog feature request libcudf strings
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

**Is your feature request related to a problem? Please describe.**
The issue documents a few performance ideas for the libcudf regular expression engine ([code pointer](https://github.com/rapidsai/cudf/tree/branch-24.06/cpp/src/strings/regex)) and strings APIs. In particular, these performance ideas came from investigation of multi-string pattern matching commonly used for IP addresses in DPUs. The DPU use case involves checking dozens (?) of string patterns against millions (?) of input strings, and most matches are negative.

| Idea | API scope | Initial scoping |
|---|---|---|
| Avoid regex and instead replace with strings contains or strings startswith/endswith whenever possible. | regex utilities | For now we encourage libcudf applications to add pattern inspection and avoid calling the regex engine if that is an important optimization in their use case. We may consider upstreaming a tool similar to the [regex parsing approach in Spark-RAPIDS](https://github.com/NVIDIA/spark-rapids/pull/10715) at some point. |
| Add a non-regex multi-string match function to the strings API, as a way to fused multiple string matches into a single kernel | strings | We have an investigation of this idea in #15536. Performance analysis is in progress |
| Use a shared memory Shift-Or approach to speed up strings contains. | strings | Initial scoping suggests this method could deliver 3x throughput (~1000 GB/s on A100). However this optimization will have a larger memory footprint (256 bytes/thread) that could create other issues when integrated with libcudf. ([link to algorithm demonstration](https://www.educative.io/answers/shift-or-string-matching-algorithm)) |
| Fuse sequences of regex pattern characters into a single "regex literal" token | regex | After initial scoping, multi-character pattern tokens are unlikely to be compatible with the existing regex engine. Significant refactoring would be required and the benefits are uncertain. |
| ASCII-only strings `contains` | strings | There may be benefit to an ASCII-only implementation of string matching for some use cases. The potential performance benefit has not yet been evaluated. |
| ASCII-only `match_re` | strings | There may be benefit to an ASCII-only implementation of regex pattern matching for some use cases. The potential performance benefit has not yet been evaluated. |
| [Sitaridi et al 2016](https://dl.acm.org/doi/pdf/10.1007/s00778-015-0409-y) suggests to use Knuth–Morris–Pratt (KMP) for string pattern matching | strings | Stores a partial match table that improves GPU L2 cache utilization |
| add aligned strings for vector loading | strings | add padding in the byte array, add sizes child column. always use aligned strings by default? |
| prefix strings | strings | see Arrow (TBD) |

**Describe the solution you'd like**
TBD

**Describe alternatives you've considered**
TBD

**Additional context**
Regex performance ideas have come out of collaboration between SM-based and DPU-based regular expression processing. For more information about DPU-based regex, please see the [NVIDIA Bluefield-2](https://docs.nvidia.com/networking/display/bluefielddpuosv385/regex+acceleration) docs.

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.