Tips for improving encoding time for large vecs/hashmaps?

[joshuataylor]

Hi!

I'm writing a library for Elixir which deserialises Apache Arrow, specifically the IPC streaming files using arrow2 , then returning them back to Elixir as rows. Using Rustler for this has been an amazing experience, and has taught me a lot about Rust (as a Rust beginner).

This is for a Snowflake adapter for Elixir, they return both JSON/Arrow and from my initial benchmarks when Snowflake sends Arrow it returns 2-3x faster compared to JSON.

I seem to have hit a problem when returning a large amount of strings back to Elixir, as it needs to encode each one? Maybe there is a more efficient way to return data?

Here is an example repo I have: https://github.com/joshuataylor/serde_examples

git clone https://github.com/joshuataylor/serde_rustler
cd serde_rustler
mix deps.get
# You'll need rust, for this
MIX_ENV=bench mix run lib/benchmarks

My results across three different systems:

1/ My desktop, a 32 core threadripper 2990wx, designed for multicore not as much single threaded :)

Operating System: Linux
CPU Information: AMD Ryzen Threadripper 2990WX 32-Core Processor
Number of Available Cores: 64
Available memory: 125.75 GB
Elixir 1.13.4
Erlang 25.0

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 1.40 min

Benchmarking hashmap of size 100 with 30,000 integer items ...
Benchmarking hashmap of size 100 with 30,000 str items ...
Benchmarking hashmap of size 100 with 30,000 string items ...
Benchmarking hashmap of size 4 vec with 30,000 integer items ...
Benchmarking hashmap of size 4 vec with 30,000 string items ...
Benchmarking hashmap of size 4 with 30,000 str items ...
Benchmarking vec with 100 integer items ...
Benchmarking vec with 100 str items ...
Benchmarking vec with 100 string items ...
Benchmarking vec with 30,000 integer items ...
Benchmarking vec with 30,000 str items ...
Benchmarking vec with 30,000 string items ...

Name                                                      ips        average  deviation         median         99th %
vec with 100 integer items                          224596.04     0.00445 ms   ±272.73%     0.00437 ms     0.00526 ms
vec with 100 str items                               28490.19      0.0351 ms   ±116.05%      0.0214 ms        0.22 ms
vec with 100 string items                            22930.98      0.0436 ms    ±88.19%      0.0304 ms        0.22 ms
vec with 30,000 integer items                         3420.43        0.29 ms    ±32.16%        0.23 ms        0.44 ms
hashmap of size 4 vec with 30,000 integer items        799.12        1.25 ms    ±20.59%        1.07 ms        1.80 ms
vec with 30,000 str items                              124.86        8.01 ms    ±36.03%        7.18 ms       11.35 ms
vec with 30,000 string items                           104.46        9.57 ms    ±27.90%        8.28 ms       12.72 ms
hashmap of size 4 with 30,000 str items                 28.71       34.83 ms    ±37.95%       34.50 ms       50.27 ms
hashmap of size 4 vec with 30,000 string items          23.77       42.07 ms    ±31.14%       41.78 ms       59.60 ms
hashmap of size 100 with 30,000 integer items           16.39       61.03 ms    ±30.10%       48.28 ms       95.36 ms
hashmap of size 100 with 30,000 str items                0.79     1261.12 ms    ±35.46%     1235.97 ms     1832.85 ms
hashmap of size 100 with 30,000 string items             0.68     1480.41 ms    ±30.67%     1462.82 ms     2053.02 ms

Comparison: 
vec with 100 integer items                          224596.04
vec with 100 str items                               28490.19 - 7.88x slower +0.0306 ms
vec with 100 string items                            22930.98 - 9.79x slower +0.0392 ms
vec with 30,000 integer items                         3420.43 - 65.66x slower +0.29 ms
hashmap of size 4 vec with 30,000 integer items        799.12 - 281.06x slower +1.25 ms
vec with 30,000 str items                              124.86 - 1798.79x slower +8.00 ms
vec with 30,000 string items                           104.46 - 2150.13x slower +9.57 ms
hashmap of size 4 with 30,000 str items                 28.71 - 7823.25x slower +34.83 ms
hashmap of size 4 vec with 30,000 string items          23.77 - 9448.26x slower +42.06 ms
hashmap of size 100 with 30,000 integer items           16.39 - 13706.17x slower +61.02 ms
hashmap of size 100 with 30,000 str items                0.79 - 283241.75x slower +1261.11 ms
hashmap of size 100 with 30,000 string items             0.68 - 332494.03x slower +1480.40 ms

A desktop 6 core 5600x, pretty decent single core performance.

Operating System: Linux
CPU Information: AMD Ryzen 5 5600X 6-Core Processor
Number of Available Cores: 12
Available memory: 31.26 GB
Elixir 1.13.4
Erlang 25.0

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 1.40 min

Benchmarking hashmap of size 100 with 30,000 integer items ...
Benchmarking hashmap of size 100 with 30,000 str items ...
Benchmarking hashmap of size 100 with 30,000 string items ...
Benchmarking hashmap of size 4 vec with 30,000 integer items ...
Benchmarking hashmap of size 4 vec with 30,000 string items ...
Benchmarking hashmap of size 4 with 30,000 str items ...
Benchmarking vec with 100 integer items ...
Benchmarking vec with 100 str items ...
Benchmarking vec with 100 string items ...
Benchmarking vec with 30,000 integer items ...
Benchmarking vec with 30,000 str items ...
Benchmarking vec with 30,000 string items ...

Name                                                      ips        average  deviation         median         99th %
vec with 100 integer items                          440026.49     0.00227 ms   ±527.90%     0.00152 ms     0.00333 ms
vec with 100 str items                               98311.55      0.0102 ms   ±326.28%     0.00618 ms      0.0761 ms
vec with 100 string items                            75990.35      0.0132 ms   ±234.79%     0.00901 ms      0.0677 ms
vec with 30,000 integer items                         3363.90        0.30 ms    ±30.24%        0.23 ms        0.43 ms
hashmap of size 4 vec with 30,000 integer items        943.68        1.06 ms    ±17.88%        0.93 ms        1.33 ms
vec with 30,000 str items                              205.69        4.86 ms    ±34.67%        3.99 ms        6.83 ms
vec with 30,000 string items                           158.76        6.30 ms    ±26.89%        5.57 ms        8.13 ms
hashmap of size 4 with 30,000 str items                 44.00       22.73 ms    ±40.48%       21.72 ms       32.81 ms
hashmap of size 4 vec with 30,000 string items          32.72       30.56 ms    ±29.89%       30.20 ms       40.48 ms
hashmap of size 100 with 30,000 integer items           21.64       46.21 ms    ±26.00%       37.65 ms       69.52 ms
hashmap of size 100 with 30,000 str items                1.01      990.53 ms    ±29.35%      944.34 ms     1421.41 ms
hashmap of size 100 with 30,000 string items             0.89     1128.15 ms    ±26.64%     1111.75 ms     1577.29 ms

Comparison: 
vec with 100 integer items                          440026.49
vec with 100 str items                               98311.55 - 4.48x slower +0.00790 ms
vec with 100 string items                            75990.35 - 5.79x slower +0.0109 ms
vec with 30,000 integer items                         3363.90 - 130.81x slower +0.30 ms
hashmap of size 4 vec with 30,000 integer items        943.68 - 466.29x slower +1.06 ms
vec with 30,000 str items                              205.69 - 2139.25x slower +4.86 ms
vec with 30,000 string items                           158.76 - 2771.61x slower +6.30 ms
hashmap of size 4 with 30,000 str items                 44.00 - 10000.30x slower +22.72 ms
hashmap of size 4 vec with 30,000 string items          32.72 - 13446.55x slower +30.56 ms
hashmap of size 100 with 30,000 integer items           21.64 - 20335.74x slower +46.21 ms
hashmap of size 100 with 30,000 str items                1.01 - 435860.19x slower +990.53 ms
hashmap of size 100 with 30,000 string items             0.89 - 496416.95x slower +1128.15 ms

My laptop, a 2020 m1 Macbook Air:

Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.13.4
Erlang 25.0

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 1.40 min

Benchmarking hashmap of size 100 with 30,000 integer items ...
Benchmarking hashmap of size 100 with 30,000 str items ...
Benchmarking hashmap of size 100 with 30,000 string items ...
Benchmarking hashmap of size 4 vec with 30,000 integer items ...
Benchmarking hashmap of size 4 vec with 30,000 string items ...
Benchmarking hashmap of size 4 with 30,000 str items ...
Benchmarking vec with 100 integer items ...
Benchmarking vec with 100 str items ...
Benchmarking vec with 100 string items ...
Benchmarking vec with 30,000 integer items ...
Benchmarking vec with 30,000 str items ...
Benchmarking vec with 30,000 string items ...

Name                                                      ips        average  deviation         median         99th %
vec with 100 integer items                          186525.60     0.00536 ms   ±133.82%     0.00404 ms      0.0362 ms
vec with 100 str items                               51739.64      0.0193 ms   ±101.05%      0.0117 ms       0.104 ms
vec with 100 string items                            38760.47      0.0258 ms   ±136.20%      0.0144 ms       0.107 ms
vec with 30,000 integer items                         3760.79        0.27 ms    ±39.94%       0.200 ms        0.44 ms
hashmap of size 4 vec with 30,000 integer items        848.99        1.18 ms    ±26.98%        1.24 ms        1.93 ms
vec with 30,000 str items                              224.81        4.45 ms    ±37.61%        4.50 ms        7.41 ms
vec with 30,000 string items                           169.46        5.90 ms    ±27.64%        6.40 ms        8.86 ms
hashmap of size 4 with 30,000 str items                 51.07       19.58 ms    ±38.90%       19.07 ms       29.39 ms
hashmap of size 4 vec with 30,000 string items          39.17       25.53 ms    ±29.49%       25.12 ms       35.08 ms
hashmap of size 100 with 30,000 integer items           29.37       34.05 ms    ±51.80%       21.56 ms       65.53 ms
hashmap of size 100 with 30,000 str items                1.19      842.51 ms    ±49.59%      787.23 ms     1632.54 ms
hashmap of size 100 with 30,000 string items             0.93     1071.76 ms    ±44.40%      908.49 ms     1896.11 ms

Comparison:
vec with 100 integer items                          186525.60
vec with 100 str items                               51739.64 - 3.61x slower +0.0140 ms
vec with 100 string items                            38760.47 - 4.81x slower +0.0204 ms
vec with 30,000 integer items                         3760.79 - 49.60x slower +0.26 ms
hashmap of size 4 vec with 30,000 integer items        848.99 - 219.70x slower +1.17 ms
vec with 30,000 str items                              224.81 - 829.70x slower +4.44 ms
vec with 30,000 string items                           169.46 - 1100.73x slower +5.90 ms
hashmap of size 4 with 30,000 str items                 51.07 - 3652.00x slower +19.57 ms
hashmap of size 4 vec with 30,000 string items          39.17 - 4761.35x slower +25.52 ms
hashmap of size 100 with 30,000 integer items           29.37 - 6351.49x slower +34.05 ms
hashmap of size 100 with 30,000 str items                1.19 - 157150.24x slower +842.51 ms
hashmap of size 100 with 30,000 string items             0.93 - 199910.08x slower +1071.75 ms

[filmor]

If you have a single buffer that contains all strings, you can return that one and the positions to then extract the substrings using binary:part/2. Since this will only create a bunch of views into the one buffer, I'd guess that this would be faster.

[joshuataylor]

Unfortunately it will be a mix of strings, integers, strructs, etc.

You can see an example here: https://github.com/joshuataylor/serde_examples/blob/main/native/serde_examples/src/lib.rs#L57

[filmor]

Well, in an Arrow frame it won't. The whole point of Arrow is to have a per-column homogeneous data. So you can check in the Arrow schema whether a column is a string column and return it in the way that I suggested. The relevant methods are Utf8Array::values and Utf8Array::offsets.

(I'll take the liberty of moving this into a discussion, it's not really an issue with Rustler).

[joshuataylor]

Awesome!

Thanks so much for setting up discussions, I wasn't sure where to place this (as it's not an issue as you mentioned).

wrt/ The initial thread:
Yeah, that works really well if we're returning it in columns it would work well as the types are all the same, but these are vecs vecs. as we want to transpose the columns to rows. So our data will go from this:

column1 (int32): [1,2,3,4,5,6]
column2 (string): ["a", "b", "c", "d", "e", 'f"]

To this:

[[1, "a"], [2,"b"], [3, "c"], [4, "d"], [5, "e"], [6, "f"]]

This is a specific integration with Snowflake, I'm sure we'll also have a generic NIF at some point (or people can just use polars/nx).

I also really appreciate your comments as well, the community here and over in Rust land is fantastic 🙌

edit: I'm going to do an experiment and return all columns as is, then do List.zip across the columns in Elixir

[filmor]

Well, a vec of rows is a really inefficient representation of the data, you should probably use tuples to represent the rows.

Regarding the string data, we expose the enif_make_sub_binary functionality on our binaries. So instead of generating a separate binary for each converted string, you could make use of the fact that it is already a single big buffer in Arrow, generate an Erlang binary from that (as a copy) and then use the offset information to create sub-binaries.