Up to 10x faster strings for C, C++, Python, Rust, and Swift, leveraging SWAR and SIMD on Arm Neon and x86 AVX2 & AVX-512-capable chips to accelerate search, sort, edit distances, alignment scores, etc 🦖
Fixed Address Sanitizer errors when running bench_search in debug mode. These were caused due to the conversion from a character set (i.e. sz::newlines()) to std::string resulting in strings with an incorrect length.
Address Sanitizer output
```
StringZilla. Starting search benchmarks.
Parsed the dataset with:
- 1048576 words of mean length ~ 5.12 bytes
- 32768 lines of mean length ~ 128.54 bytes
Benchmarking for a newline symbol:
- std::string_view.find 0.3006 GB/s 27902428.1 ns 0 errors in 360 iterations
- sz_find_serial 0.1551 GB/s 54083324.5 ns 0 errors in 188 iterations
- sz_find_avx2 0.4209 GB/s 19930871.6 ns 0 errors in 504 iterations
- strstr 0.0001 GB/s 134832543000.0 ns 0 errors in 4 iterations
- std::search<> 0.0217 GB/s 386564882.1 ns 0 errors in 28 iterations
- std::search 0.0081 GB/s 1030440916.7 ns 0 errors in 12 iterations
- std::search 0.0134 GB/s 627206156.2 ns 0 errors in 16 iterations
- std::string_view.rfind 0.1094 GB/s 76695712.9 ns 0 errors in 132 iterations
- sz_rfind_serial 0.1537 GB/s 54575531.0 ns 0 errors in 184 iterations
- sz_rfind_avx2 0.4247 GB/s 19749949.8 ns 0 errors in 508 iterations
- std::search 0.0173 GB/s 486119066.7 ns 0 errors in 24 iterations
- std::search 0.0075 GB/s 1120413216.7 ns 0 errors in 12 iterations
- std::search 0.0096 GB/s 874787233.3 ns 0 errors in 12 iterations
Benchmarking for an [\n\r] RegEx:
=================================================================
==15944==ERROR: AddressSanitizer: global-buffer-overflow on address 0x7ff632faeec8 at pc 0x7ff9aa6f681a bp 0x005bd8cfe160 sp 0x005bd8cfd910
READ of size 10 at 0x7ff632faeec8 thread T0
==15944==WARNING: Failed to use and restart external symbolizer!
#0 0x7ff9aa6f6819 in _asan_wrap_strlen+0x2c9 (C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.39.33519\bin\Hostx64\x64\clang_rt.asan_dynamic-x86_64.dll+0x180036819)
#1 0x7ff632f92c82 in std::_Narrow_char_traits::length C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.39.33519\include\xstring:398
#2 0x7ff632f79ac1 in std::basic_string,std::allocator >::basic_string,std::allocator > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.39.33519\include\xstring:2557
#3 0x7ff632f51dc6 in main C:\Users\ashbo\Documents\StringZilla\scripts\bench_search.cpp:298
#4 0x7ff632f9d868 in invoke_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:78
#5 0x7ff632f9d7bd in __scrt_common_main_seh D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:288
#6 0x7ff632f9d67d in __scrt_common_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:330
#7 0x7ff632f9d8dd in mainCRTStartup D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_main.cpp:16
#8 0x7ff9f7c67343 in BaseThreadInitThunk+0x13 (C:\WINDOWS\System32\KERNEL32.DLL+0x180017343)
#9 0x7ff9f7e026b0 in RtlUserThreadStart+0x20 (C:\WINDOWS\SYSTEM32\ntdll.dll+0x1800526b0)
0x7ff632faeec8 is located 0 bytes to the right of global variable '`ashvardanian::stringzilla::newlines'::`2'::all' defined in 'stringzilla.hpp:214:27' (0x7ff632faeec0) of size 8
SUMMARY: AddressSanitizer: global-buffer-overflow (C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.39.33519\bin\Hostx64\x64\clang_rt.asan_dynamic-x86_64.dll+0x180036819) in _asan_wrap_strlen+0x2c9
Shadow bytes around the buggy address:
0x11705a875d80: 00 00 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9
0x11705a875d90: 00 00 00 00 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9
0x11705a875da0: f9 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9
0x11705a875db0: f9 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 f9 f9 f9 f9
0x11705a875dc0: f9 f9 f9 f9 f9 f9 f9 f9 06 f9 f9 f9 f9 f9 f9 f9
=>0x11705a875dd0: f9 f9 f9 f9 f9 f9 f9 f9 00[f9]f9 f9 f9 f9 f9 f9
0x11705a875de0: f9 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x11705a875df0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x11705a875e00: 00 00 06 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9
0x11705a875e10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x11705a875e20: 00 00 00 00 00 02 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
```
Also increased the number of characters for bench name output, since there were names longer than 20 chars.
Fixed Address Sanitizer errors when running
bench_search
in debug mode. These were caused due to the conversion from a character set (i.e.sz::newlines()
) tostd::string
resulting in strings with an incorrect length.Address Sanitizer output
``` StringZilla. Starting search benchmarks. Parsed the dataset with: - 1048576 words of mean length ~ 5.12 bytes - 32768 lines of mean length ~ 128.54 bytes Benchmarking for a newline symbol: - std::string_view.find 0.3006 GB/s 27902428.1 ns 0 errors in 360 iterations - sz_find_serial 0.1551 GB/s 54083324.5 ns 0 errors in 188 iterations - sz_find_avx2 0.4209 GB/s 19930871.6 ns 0 errors in 504 iterations - strstr 0.0001 GB/s 134832543000.0 ns 0 errors in 4 iterations - std::search<> 0.0217 GB/s 386564882.1 ns 0 errors in 28 iterations - std::searchAlso increased the number of characters for bench name output, since there were names longer than 20 chars.