lemire / despacer Goto Github PK

View Code? Open in Web Editor NEW

147.0 10.0 15.0 1.28 MB

C library to remove white space from strings as fast as possible

License: BSD 3-Clause "New" or "Revised" License

Makefile 0.01% C 99.49% Python 0.04% CMake 0.07% Shell 0.02% D 0.37%

ascii bytes simd-programming simd ssse3 sse avx

despacer's Introduction

Hi there 👋

I am a computer science professor in the Data Science Laboratory at the Université du Québec (TÉLUQ).

📰 I write about software performance weekly on my blog.
📫 I can be reached on twitter/X.
📺 I gave a best voted talk at QCon San Francisco.
📄 I wrote over 80 research papers including over 50 journal articles, cited over 5,000 times.
📖 I am editor of the Software: Practice and Experience journal (Wiley); it was founded in 1971.

despacer's People

Contributors

Stargazers

Watchers

Forkers

4144 julienaubert shekkbuilder magurosan aqrit auserj kloetzl moneytech clayne aminya bmwtsn098 mayhemheroes zabrane sharpobject jamestiotio

despacer's Issues

The size of some tables can be reduced by half

Whether the last character is to be deleted or not is irrelevant.

credit @aqrit

Stip tabs as well

Because they are whitespaces just like \n and \r.

Include support for NEON processors

http://lemire.me/blog/2017/07/10/pruning-spaces-faster-on-arm-processors-with-vector-table-lookups/

Failed to make on Debian but succeeded on Mac OSX

suhubdyd@eos14:~/dev/despacer$ make
cc -fPIC -std=c99 -O3  -march=native -Wall -Wextra -Wshadow -o despacebenchmark ./benchmarks/despacebenchmark.c -Iinclude
In file included from ./benchmarks/despacebenchmark.c:6:0:
include/despacer.h: In function ‘cleanm256’:
include/despacer.h:377:5: warning: implicit declaration of function ‘_mm256_loadu2_m128i’ [-Wimplicit-function-declaration]
     __m256i mask = _mm256_loadu2_m128i((const __m128i *)despace_mask16 + maskhigh, (const __m128i *)despace_mask16 + masklow);
     ^
include/despacer.h:377:20: error: incompatible types when initializing type ‘__m256i’ using type ‘int’
     __m256i mask = _mm256_loadu2_m128i((const __m128i *)despace_mask16 + maskhigh, (const __m128i *)despace_mask16 + masklow);
                    ^
include/despacer.h: In function ‘avx2_despace_branchless’:
include/despacer.h:400:5: warning: implicit declaration of function ‘_mm256_storeu2_m128i’ [-Wimplicit-function-declaration]
     _mm256_storeu2_m128i((__m128i *)(bytes + pos + offset1), (__m128i *)(bytes + pos ),x);
     ^
Makefile:14: recipe for target 'despacebenchmark' failed
make: *** [despacebenchmark] Error 1

grok-machine:despacer dendisuhubdy$ make
cc -fPIC -std=c99 -O3  -march=native -Wall -Wextra -Wshadow -o despacebenchmark ./benchmarks/despacebenchmark.c -Iinclude
grok-machine:despacer dendisuhubdy$ ./despacebenchmark 
pointer alignment = 4096 bytes 
memcpy(tmpbuffer,buffer,N):  0.082031 cycles / ops
countspaces(buffer, N):  2.191406 cycles / ops
countspaces32(buffer, N):  0.730469 cycles / ops
despace(buffer, N):  1.578125 cycles / ops
despace32(buffer, N):  1.074219 cycles / ops
faster_despace(buffer, N):  1.318359 cycles / ops
faster_despace32(buffer, N):  1.609375 cycles / ops
despace64(buffer, N):  1.353516 cycles / ops
despace_to(buffer, N, tmpbuffer):  1.441406 cycles / ops
avx2_countspaces(buffer, N):  0.078125 cycles / ops
avx2_despace(buffer, N):  1.398438 cycles / ops
avx2_despace_branchless(buffer, N):  0.218750 cycles / ops
avx2_despace_branchless_u2(buffer, N):  0.205078 cycles / ops
sse4_despace(buffer, N):  0.486328 cycles / ops
sse4_despace_branchless(buffer, N):  0.320312 cycles / ops
sse4_despace_branchless32(buffer, N):  0.320312 cycles / ops
sse4_despace_branchless_u2(buffer, N):  0.203125 cycles / ops
sse4_despace_branchless_u4(buffer, N):  0.210938 cycles / ops
sse4_despace_branchless_mask8(buffer, N):  0.431641 cycles / ops
sse4_despace_trail(buffer, N):  1.126953 cycles / ops
sse42_despace_branchless(buffer, N):  0.496094 cycles / ops
sse42_despace_branchless_lookup(buffer, N):  0.501953 cycles / ops
sse42_despace_to(buffer, N,tmpbuffer):  1.050781 cycles / ops

It would be nice to add has_space function. Currently, there is a avx2_countspaces, which counts all the number of spaces. I think it is possible to add another function to return true as soon as it finds space.

Use `-march=haswell` or similar flags instead of `-march=native`

The CMake file uses -march=native, which generates binaries that are not usable on other machines that might lack the instruction set.
I think the better approach would be to use -march=haswell, which is a good default these days.

For avx512, a CMake option could be exposed.

despacer/CMakeLists.txt

Lines 17 to 19 in 579530b

    
             target_compile_options(despacer PRIVATE /arch:native) 
        
           else() 
        
             target_compile_options(despacer PRIVATE -march=native)

-march=haswell includes AVX2 and older SSE instruction sets :
https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html

Mistakes in sse4_despace_branchless_mask8

I found a few mistakes in sse4_despace_branchless_mask8(.), they probably don't influence benchamerk results but prevent it from generating correct string:

_mm_or_si128(m1,m2) should be replaced with _mm_and_si128(m1,m2), because 0xFF & x == x, 0xFF | x = 0xFF .
Tables are probably wrong too (on Intel CPUs). First line of despace_mask8_1 should look:

0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x8,0x9,0xA,0xB,0xC,0xD,0xE,0xF,

instead of:

0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x7,0x6,0x5,0x4,0x3,0x2,0x1,0x0,

First line of despace_mask8_2 should look:

0x0,0x1,0x2,0x3,0x4,0x5,0x6,0x7,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,

instead of:

0xf,0xe,0xd,0xc,0xb,0xa,0x9,0x8,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,

Go faster by defining a space character as a character with code value <=32

Find indices of white spaces within string

Amazing, amazing work!

Just thought of mentioning here that I would love to see this tweaked a bit such that, with the help of your simdprune library, one could find the indices of the white spaces chars within a given char string - instead of removing them. That would be of tremendous help in numerous string cleaning tasks.

faster despace64

parts of HASZERO/HASVALUE can be eliminated if not matching signed bytes
other parts can be deferred & combined when checking multiple values

https://gist.github.com/aqrit/6e73ca6ff52f72a2b121d584745f89f3

other things of interest in that gist (speeds unknown)

swar method for removing bytes from a word
sse2 using prefix sums and lots of shifting
ssse3 using 1024 byte lut

	target_compile_options(despacer PRIVATE /arch:native)
	else()
	target_compile_options(despacer PRIVATE -march=native)