NVIDIA / NVIDIA/cudf

[FEA] Better scaling for simple regular expressions on long strings

Open
#14,087 2 comments 1 reaction 0 assignees View on GitHub
0 - Backlog feature request Performance Spark 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.**
In Spark we have had multiple customers that try to process really long strings with simple regular expressions. The reality is that in most cases they don't need a regular expression but the API/expression Spark exposes is for a regular expression so they use it. An example of this is string split, where what is being split on is a regular expression. They will split on things like a comma `,` or try to parse JSON like formatted strings by splitting on `}` or `}}` sequences. But they do this on very large strings. Strings that are over 120KiB in size. When this happens we see really bad performance on the GPU. Even worse than single threaded performance on the CPU to process the same data. Here is an example where we are essentially doing an `explode(split(column_name, "}}"))` on 500 rows. It is 500 rows, because the length of the strings involved end up making that about 1 row group in parquet, so this is the data that a single Spark task sees.

String Length | GPU Median Time | CPU Median Time | Hacked GPU Median Time
-- | -- | -- | --
10 | 316 | 249 | 395
100 | 321 | 298 | 371
1,000 | 333 | 753 | 377
10,000 | 1,352 | 5,401 | 407
20,000 | 4,914 | 10,630 | 459
40,000 | 15,810 | 21,261 | 564
80,000 | 66,409 | 43,487 | 773
100,000 | 111,781 | 54,989 | 902
120,000 | 134,409 | 66,066 | 1,035
140,000 | 212,333 | 76,900 | 1,232

![chart(1)](https://github.com/rapidsai/cudf/assets/3441321/70bc2bb0-6eea-4c26-95df-33b397a0c567)

In this the `Hacked GPU Median Time` is when I hacked the Spark plugin to ignore the regular expression and instead use the non-regular expression CUDF API to split the string.

**Describe the solution you'd like**
In the Rapids Plugin we have put in place a number of optimizations where we will parse the regular expression and if possible transpile it to a string that we can do a non regular expression split on. We think it is worth pushing this type of optimization into CUDF itself and not just for splits. It would really be nice if CUDF could spend time to look for alternative ways to execute a regular expression, especially for really long string, that don't need a single thread per string to work properly.

Examples include

* Seeing if a regular expression can be transpiled to static string and using an alternative string operation instead. This could apply to split, matches, etc.
* When just checking if a regular expression matches a string we could match things like `FOO.*` and convert it into a starts with operation instead. This could also apply to contains or ends with.

I would like it in CUDF because I think it would benefit everyone, not just the Spark plugin, but also I think the RAPIDS team could do a better job in many cases of finding these optimizations than we are doing.

**Describe alternatives you've considered**
Update our own regular expression checker code to start doing more of these optimizations.

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.