Regarding SIMD performance

[pauljurczak]

I've run a few tests on an AMD Ryzen 7 3800X 8-core CPU and observed a decreased performance with SIMD build. Here are the results for the same input file trees.json, demanding 41 copies of a simple non-convex polygon. All runs were with 7 workers and early termination disabled.

• strip_width 3.8635 achieved in 1 hour with spyrrow
• strip_width 3.8449 achieved in 2 hours with spyrrow
• strip_width 3.8745 achieved in 1 hour with --release --features=only_final_svg
• strip_width 3.9133 achieved in 1 hour with --release --features=simd,only_final_svg

For some reason, SIMD version produced the worst result. I successfully installed the nightly build and configured my session with:

export RUSTFLAGS='-C target-cpu=native'
export RUSTUP_TOOLCHAIN=nightly

Is there a way to double-check that SIMD instructions were actually used? My CPU supports up to AVX2 instructions.

[JeroenGar]

Hi Paul,

sparrow is a non-deterministic algorithm.
Solution quality, therefore, is not a direct product of the performance of the code (which is increased in the SIMD version).

The best way to measure the speed/throughput is to look at the eval/s metric, which is periodically reported in the logs.
Although this metric varies throughout the optimization, you should be able to see that the maximum reported eval/s increases when SIMD is enabled.

To identify any improvements or regressions in solution quality, each configuration has be benchmarked many times (>25x) and averaged.

Hope this helps you with solving the Christmas Tree Packing Challenge on Kaggle ;)

Best,
Jeroen

[pauljurczak]

Hi Jeroen,

Thank you for quick response. Yes, I'm aware of non-deterministic performance, probably amplified by not using the same seed value for each run. I've run the tests a few times now, and there is SIMD improvement on average. I was trying to find an imperfect performance metric. The eval/s metric varies wildly, e.g. 1758 K to 3342 K. The ranges overlap between SIMD and non-SIMD versions and the difference looks small without applying statistical analysis to log files. Do you have an estimate how much faster the SIMD version should be?

Thanks,
Paul

[pauljurczak]

I have the measurements of evals/s, excluding zero values, for Intel Core Ultra 5 125H CPU (18 logical cores) running Ubuntu 24.04 with different n_workers on the same 1-hour task. Shown are minimum, median and maximum values.

n_workers = 9
SIMD:  1242 2440 2904
none:  1024 1883 2450

n_workers = 12
SIMD:  1771 2918 3759
none:  1280 2238 2928

n_workers = 18
SIMD:  1827 3387 4675
none:  1753 2630 3907

There is only 30% speedup with SIMD on this system.

[JeroenGar]

Hi Paul,

This look about what I would expect.
My system (AMD 7950X, 3 workers) reaches about 2400K/s with simd feature and 2000K/s without.

The only thing the simd feature enables is a handwritten SIMD version of the quantification function (see here).
About 30% of the total compute time is spent inside this function.
It is not surprising that the gains are not more pronounced.

Also, the compiler does auto-vectorization on its own.
If you were to compile for a generic x86 CPU, so without export RUSTFLAGS='-C target-cpu=native', you will see a larger discrepancy.

Best,
Jeroen

Just a tip: from my experience, using >4 workers yields worse solutions on average.

[pauljurczak]

Here are my results with 41 trees, 1-hour run with strip_height: 3.87:

Box	Dims	Time	SIMD	Workers	evals/s	CPU
41	3.87 x 3.9194	1	no	18	2630	Ultra 5 125H
41	3.87 x 3.8383	1	yes	18	3387	Ultra 5 125H
41	3.87 x 3.8779	1	no	9	1883	Ultra 5 125H
41	3.87 x 3.8994	1	yes	9	2440	Ultra 5 125H
41	3.87 x 3.8650	1	no	12	2238	Ultra 5 125H
41	3.87 x 3.8395	1	yes	12	2918	Ultra 5 125H

Surprisingly, 18 workers produced both the best and the worst result, 12 workers did better than 9, but this is based only on a single run for each configuration.