Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Leveraging SIMD: Splitting CSV Files at 3Gb/S

blog.tinybird.co

Post reply on HN
Print view View original

21–30 of 43 posts

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#21

Post by pclmulqdq »

zwegner wrote: post #2

Pretty similar article from very recently: https://nullprogram.com/blog/2021/12/04/ Discussion: https://news.ycombinator.com/item?id=29439403 The article mentions in an addendum (and BeeOnRope also pointed it out in the HN thread) a nice CLMUL trick for dealing with quotes originally discovered by Geoff Langdale. That should work here for a nice speedup. But without the CLMUL trick, I'd guess that the unaligned loads…

The carryless multiplication instructions are amazing and people should use them more often. They are just so poorly explained that they feel like magic.

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#22

Post by gpderetta »

davidm1729 wrote: post #17
zwegner wrote: post #2

Pretty similar article from very recently: https://nullprogram.com/blog/2021/12/04/ Discussion: https://news.ycombinator.com/item?id=29439403 The article mentions in an addendum (and BeeOnRope also pointed it out in the HN thread) a nice CLMUL trick for dealing with quotes originally discovered by Geoff Langdale. That should work here for a nice speedup. But without the CLMUL trick, I'd guess that the unaligned loads…

Hi, I'm one of the authors of the post Thanks for pointing us to CLMUL, I'm not familiar with these kind of multiplications, but, converting the quote bitmask to a quoted bitmask would certainly make it faster. With this new bitmask, we could negate it and AND it with the newline mask, generating a mask of newlines that are not inside quotes. Getting the last newline then would be a simple CLZ of that mask. And there…

CLMUL is quite interesting. I learned about it when going in depth on how multiplications help with hashing.

A multiplication is in practice: - a sum over - a series (i.e. one for each bit set in the multiplier) - of shifts (where the shift amount is the index of that bit in the multiplier)

The shifting and the combining are great for hashing as they "distribute" each bit around.

CLMUL simply replaces the addition in step one with xor (which can also be thought as the single bit carryless addition).

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#23

Post by liuliu »

Splitting CSV file into chunks and process them independently won't necessarily be wrong (although there are implementations out there that I won't name would, because they do guess). The trick however requires to scan twice: https://liuliu.me/eyes/loading-csv-file-at-the-speed-limit-o...

Nice article otherwise!

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#24

Post by jagrsw »

HPsquared wrote: post #20
jagrsw wrote: post #7

Not sure how the author of this entry on HN managed to change original title from gigabytes per second to gigabits per siemens :)

Staying with Physics, "Gb/S" is Gigabarns per Siemens. Some relation of electrical conductance with cross-sectional area. The barn is a unit of cross-sectional area, based on the Uranium nucleus (area 1 barn). Uranium is pretty large in atomic terms; the name is from the idiom "couldn't hit the broad side of a barn".

And since 1/S = 1Ω, it'd be Gigabarnohm.

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#25

Post by jwandborg »

mschuster91 wrote: post #10
__s wrote: post #5

Earlier quoted context omitted.

Python's csv imports _csv for core functionality, which is C: https://github.com/python/cpython/blob/main/Modules/_csv.c

Thanks! Updated accordingly.

You should update "all sans PHP" to reflect the update.

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#26

Post by jwandborg »

nickpeterson wrote: post #9
mschuster91 wrote: post #4

Earlier quoted context omitted.

If you're doing user-supplied CSVs, definitely... but if you are ingesting CSVs from a known source with known format ( ) it can definitely make sense to use a high-speed optimized ingester. One might wonder if it might be worth the time to look into optimising the runtimes of various languages. I took a look, all operate on naive byte-by-byte scanning, and all sans PHP are written in the respective language which me…

It’s funny, csv files are so common and yet many mainstream languages don’t even attempt a decent parser baked in. I think dotnet has 3-4 different ones and as I recall they’re all pretty slow.

There's multiple dialects of CSV. Besides the more standardish dialect there are some weird ones that prevent some types of optimization. I remember Apple's "Enterprise Partner Feed" had a dialect I've never seen elsewhere so far. Columns were separated by 0x01, rows were separated by 0x02 0x0A.

The row separator being two bytes throws a wrench in most parsers.

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#27

Post by ipdashc »

jwandborg wrote: post #26
nickpeterson wrote: post #9

Earlier quoted context omitted.

It’s funny, csv files are so common and yet many mainstream languages don’t even attempt a decent parser baked in. I think dotnet has 3-4 different ones and as I recall they’re all pretty slow.

There's multiple dialects of CSV. Besides the more standardish dialect there are some weird ones that prevent some types of optimization. I remember Apple's "Enterprise Partner Feed" had a dialect I've never seen elsewhere so far. Columns were separated by 0x01, rows were separated by 0x02 0x0A. The row separator being two bytes throws a wrench in most parsers.

What a bizarre choice. If they're going to commit to weird ASCII control chars you'd think they could just use 0x1C to 0x1F, which are explicitly intended as delimiters/Separators... sigh. (I've always wondered why more people don't use the various Separators, but I admit human-readability is a big advantage)

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#28

Post by mschuster91 »

jwandborg wrote: post #26
nickpeterson wrote: post #9

Earlier quoted context omitted.

It’s funny, csv files are so common and yet many mainstream languages don’t even attempt a decent parser baked in. I think dotnet has 3-4 different ones and as I recall they’re all pretty slow.

There's multiple dialects of CSV. Besides the more standardish dialect there are some weird ones that prevent some types of optimization. I remember Apple's "Enterprise Partner Feed" had a dialect I've never seen elsewhere so far. Columns were separated by 0x01, rows were separated by 0x02 0x0A. The row separator being two bytes throws a wrench in most parsers.

> The row separator being two bytes throws a wrench in most parsers.

Huh? Anything that ingests Windows-origin files needs to be capable with \r\n by default.

Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S

#30

Post by robertlagrant »

jagrsw wrote: post #24
HPsquared wrote: post #20

Earlier quoted context omitted.

Staying with Physics, "Gb/S" is Gigabarns per Siemens. Some relation of electrical conductance with cross-sectional area. The barn is a unit of cross-sectional area, based on the Uranium nucleus (area 1 barn). Uranium is pretty large in atomic terms; the name is from the idiom "couldn't hit the broad side of a barn".

And since 1/S = 1Ω, it'd be Gigabarnohm.

Hence the old joke: how many Gigabarnohms does it take to start a circus?

Answer, of course, one million.

Post reply on HN