[BUG] Operations with string_view involving character counting are very inefficient

[ttnghia]

Due to the nature of strings columns that they only contain offsets to determine string boundaries, there is no way to know in O(1) how many characters were stored in each string. As such, when an operation requires to know the number of characters, an expensive sequential count is executed:

return thrust::count_if(
    thrust::seq, ptr, ptr + bytes, [](uint8_t chr) { return is_begin_utf8_char(chr); });

Because of that, a simple operation like substr can be extremely expensive. One of my tests with 1.4 million (customized) substring ops from just one source string can be slow like this:

|  test_size  | Samples |  CPU Time  | Noise |  GPU Time  | Noise |  Elem/s  | bytes_per_second | peak_memory_usage |
|-------------|---------|------------|-------|------------|-------|----------|------------------|-------------------|
|   2^8 = 256 |     34x | 451.036 ms | 1.62% | 450.978 ms | 1.62% |   8.287M |          8287194 |        35.142 MiB |
| 2^12 = 4096 |      1x |   96.397 s |  inf% |   96.393 s |  inf% | 620.353K |           620353 |       562.277 MiB |

When I just use the simple way of memcpy (which cannot deal with utf8 character, assuming that the input only has ASCII) then the performance went back to be reasonable:

|  test_size  | Samples | CPU Time  | Noise | GPU Time  | Noise |  Elem/s  | bytes_per_second | peak_memory_usage |
|-------------|---------|-----------|-------|-----------|-------|----------|------------------|-------------------|
|   2^8 = 256 |   1899x |  7.884 ms | 4.23% |  7.879 ms | 4.22% | 474.344M |        474344125 |        35.142 MiB |
| 2^12 = 4096 |    788x | 19.030 ms | 2.86% | 19.024 ms | 2.86% |   3.143G |       3143281474 |       562.277 MiB |

Summary for the tables above: using just memcpy for substring without character counting can improve performance from 96 seconds down to 19 milliseconds.

As such, the way of implementing strings column should be improved. We may need to have some efficient way to compute the number of characters in parallel (such as using thrust::reduce_by_key), or have a new way to store strings such that we can compute the number of characters in O(1) time.

I don't have a very good idea of how to implement and use those efficiently for various internal string_view operations but they should be on the table. Otherwise, we will hit this performance issue more in the future.

[ttnghia]

CC @davidwendt for visibility.

[davidwendt]

Recommend not using cudf::string_view for parsing JSON. The class is useful when dealing with characters and character offsets. The substr() and find() function accept character positions and lengths as needed by various functions.