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

Show HN: Parsing CSV files with GPU

github.com

Post reply on HN
Print view View original

41–50 of 63 posts

Re: Show HN: Parsing CSV files with GPU

#41

Post by infogulch »

TheLoneWolfling wrote: post #39
haberman wrote: post #36

Earlier quoted context omitted.

This is a perfect example of how text parsing is really inherently non-parallelizable. It's very rare that you can do anything useful with a buffer of text without knowing the precise state of the parse at the beginning of that buffer. The kinds of patterns that would make parsing more parallelizable, like marking the beginning of a delimited region with its length, are human unfriendly so would never be part of an a…

And that's why you let the computer do it for you.

And now that you're using a computer to do it you might as well use protobuf or bson or.... But then it's not a plain text format anymore and we're back to square one.

Re: Show HN: Parsing CSV files with GPU

#42

Post by wfunction »

haberman wrote: post #36
kazinator wrote: post #29

Though there is no standard definition of CSV, de facto processing it properly requires recognizing quotes, and also escapes of literal quotes using double quoting: this, "is, like, CSV", "with three so-called ""fields""" Note that unquoted leading and trailing whitespace, and whitespace around the commas, is deleted, too. (See CSV page in the Wikipedia) A GPU-accelerated string split could be useful but it's not qui…

This is a perfect example of how text parsing is really inherently non-parallelizable. It's very rare that you can do anything useful with a buffer of text without knowing the precise state of the parse at the beginning of that buffer. The kinds of patterns that would make parsing more parallelizable, like marking the beginning of a delimited region with its length, are human unfriendly so would never be part of an a…

I've always wondered if parsing is still unparallelizable if you also allow backtracking. In other words, can you parse eagerly assuming that you're likely to be in a certain state, and then if you're proven wrong maybe you can retry?

Re: Show HN: Parsing CSV files with GPU

#43

Post by maxhou »

In the real world, the slow part of "parsing" a CSV file is IO: reading the file content from disk to memory, and from memory to CPU cache.

You would avoid reading the file content more than once if you had to parse it.

> The first line counts the number of lines in a buffer (assuming that file is read into memory and copied to gpu buffer d_readbuff).

but this is what is done here, first search to find all \n, then multi-core GPU stuff for each line content.

Re: Show HN: Parsing CSV files with GPU

#44

Post by azurezyq »

maxhou wrote: post #43

In the real world, the slow part of "parsing" a CSV file is IO: reading the file content from disk to memory, and from memory to CPU cache. You would avoid reading the file content more than once if you had to parse it. > The first line counts the number of lines in a buffer (assuming that file is read into memory and copied to gpu buffer d_readbuff). but this is what is done here, first search to find all \n, then m…

Things have been changed in a world of SSDs and machines w/ much memory. Actually, parsing a CSV in a single thread will never reach several hundred megabytes per second.

Re: Show HN: Parsing CSV files with GPU

#45

Post by andrewguenther »

This title is incredibly misleading.

* This isn't parsing a CSV, this is a program written to split this exact dataset. (The code is filled with hard coded values)

* You're comparing a single-threaded run on a low-end CPU to a top-tier GPU.

* Your dataset can fit into GPU memory.

* There is a pull request for a missing semicolon, which means the posted version of the code won't even compile, so couldn't have been the version used to generate the benchmarks.

* The amount of branching in the GPU code makes it hard for me to believe that it actually ran that fast. GPU parallelism does not work well with branching since all cores in a cube must executing in lock-step, if you branch, then you now have to go back and execute all of your branches separately.

Re: Show HN: Parsing CSV files with GPU

#46

Post by [deleted] »

zvrba wrote: post #20
castratikron wrote: post #14

I'm skeptical of the 8x speedup for several reasons, the main one being that this particular problem does not fit the paradigm of problems that work well on the GPU; the GPU cache is not used at all, and there are also many branches. You need to be able to use the cache of the GPU in your application, otherwise your performance is guaranteed to be memory-bound. The reason you want to avoid branches is that there is o…

> I'm skeptical of the 8x speedup for several reasons [...] yet the CPU is only running a single thread That's why I'm not skeptical at all. A GPU program can operate over THOUSANDS many more data items in parallel than a single-threaded scalar CPU program can. Yet the speedup is not thousands, not even hundreds, but a mere 8. Fits perfectly with > main one being that this particular problem does not fit the paradigm…

[deleted]

Re: Show HN: Parsing CSV files with GPU

#47

Post by maxhou »

victorNicollet wrote: post #27
bane wrote: post #26

Earlier quoted context omitted.

And if you're going to load it, you may as well parse it on the way in.

A streaming CSV parser is very difficult to get right, once you get past a certain level of complexity. Sometimes, you are not lucky enough to have perfect control over the encoding, number format and date format of the input, so you need to look ahead at a value sample to try and find out what those are. Sometimes, you cannot even assume that the software that produced the file didn't mangle the quotes around fields…

if you use mmap(), there is virtualy no difference between the streaming/non streaming parsing code.

Re: Show HN: Parsing CSV files with GPU

#48

Post by pcwalton »

haberman wrote: post #36
kazinator wrote: post #29

Though there is no standard definition of CSV, de facto processing it properly requires recognizing quotes, and also escapes of literal quotes using double quoting: this, "is, like, CSV", "with three so-called ""fields""" Note that unquoted leading and trailing whitespace, and whitespace around the commas, is deleted, too. (See CSV page in the Wikipedia) A GPU-accelerated string split could be useful but it's not qui…

This is a perfect example of how text parsing is really inherently non-parallelizable. It's very rare that you can do anything useful with a buffer of text without knowing the precise state of the parse at the beginning of that buffer. The kinds of patterns that would make parsing more parallelizable, like marking the beginning of a delimited region with its length, are human unfriendly so would never be part of an a…

> This is a perfect example of how text parsing is really inherently non-parallelizable. It's very rare that you can do anything useful with a buffer of text without knowing the precise state of the parse at the beginning of that buffer.

There are two mechanisms that are usually used to get around this:

(1) Perform a fast, sequential "skeleton parsing" pass before the main parse that scans just enough to find "split points" that are consumed by the parallel parser. This is what some of the parallel XML parsing work [1] did.

(2) Guess the state you're in based on some heuristics, and roll back on failure. This actually works surprisingly well in practice for many grammars, for example HTML [2].

[1]: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=410047...

[2]: http://www.cs.wm.edu/~xshen/Publications/taco14.pdf

Re: Show HN: Parsing CSV files with GPU

#49

Post by paulmd »

I kinda suspect he might be measuring the time it takes to launch a kernel rather than the time it takes the kernel to complete.

Thrust device calls, like those of the underlying CUDA library, are asynchronous by default. The only exception is calls that result in a memcpy, which are synchronous. To wait until an async call is completed you need to call one of the synchronize commands, like cudaDeviceSynchronize.

Looking through his test.cu file, he snaps a timestamp using std::clock right after doing the kernel launch with for_each. Ignoring the fact that this is not an accurate way to benchmark a GPU (you need to use events to accurately benchmark the kernel) what you're capturing will just be the processor time it takes to make the async kernel launch. Std::clock measures CPU time, which is (rightly) close to 0 for a program that runs on the GPU.

It's entirely possible that you're not even getting valid results out of the other end - note that you don't show output. I don't know if thrust's magic device memory access function triggers a synchronization or not. I kinda remember having to make an explicit call when I did a GPU simulation.

I don't have access to a CUDA box at the moment, I'd have to add those cudaDeviceSynchronize calls after the for_each invocations to be sure.

Re: Show HN: Parsing CSV files with GPU

#50

Post by andrewguenther »

paulmd wrote: post #49

I kinda suspect he might be measuring the time it takes to launch a kernel rather than the time it takes the kernel to complete. Thrust device calls, like those of the underlying CUDA library, are asynchronous by default. The only exception is calls that result in a memcpy, which are synchronous. To wait until an async call is completed you need to call one of the synchronize commands, like cudaDeviceSynchronize. Loo…

I had suspected this as well, but I'm not familiar with how Thrust's CUDA bindings work.
Post reply on HN