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

51–60 of 63 posts

Re: Show HN: Parsing CSV files with GPU

#51

Post by paulmd »

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…

There's also just the sheer bandwidth factor. A GTX Titan has 288 GB/s of BW, a Haswell with DDR3 puts out about 35 GB/s. That's a factor of 8.22x more bandwidth, so there's your 8x speedup.

It's a highly memory-limited task so I suspect that's where any speedup would come from.

Re: Show HN: Parsing CSV files with GPU

#52

Post by paulmd »

stephen272 wrote: post #19
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…

You hit the nail on the head. All of that on top of the fact that he is comparing a top of the line GPU against a mediocre i3 processor. GPU to CPU comparisons are always apples to oranges, but this is pretty bad. I would like to see an OpenCL kernel that is run on both the GPU and CPU to possibly even the playing field a little.

You can compile Thrust using a device target of OpenMP, so no need to rewrite it in OpenCL.

Re: Show HN: Parsing CSV files with GPU

#54

Post by antonmks »

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…

Thrust CUDA calls are synchronous to each other. You can add an explicit synchronization call cudaDeviceSynchronize() and there won't be a difference in results.

Re: Show HN: Parsing CSV files with GPU

#55

Post by antonmks »

andrewguenther wrote: post #45

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…

Sorry if you are misled :-) The program does parses selected fields, there are strings-to-binaries procedures.

I tested this approach on multiterabyte files, take a look at my alenka project, it uses the same method to load large CSV files into databases. It just have to be done in chunks.

The program compiles fine, that pull request was referring to incorrect earlier version of test.cu file.

Test it for yourself, see if you get similar results.

Re: Show HN: Parsing CSV files with GPU

#56

Post by TheLoneWolfling »

wfunction wrote: post #42
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…

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?

Yes, and that's exactly what a lot of things do.

The problem with this is that you can do worse than single-threaded (although not asymptotically speaking) in the worst case.

Consider what happens if you've got something along the lines of the following:

    ",",",",",",",",","
If every parser thread (but the first, the one parsing from the start, of course) picks the wrong parity (i.e. if they should start quoted or not) repeatedly, you end up throwing away all the work of every thread but the first. And meanwhile, your first thread has to do the additional work of figuring out when to invalidate the other threads.

This is unlikely to happen, but definitely possible.

It's vaguely similar to recursive descent parsing, with vaguely similar drawbacks too.

One other similar approach is to parse eagerly as you say, but with a higher-priority thread that goes through the thread from the start only keeping track of as much state as is necessary, checking / invalidating the other threads as necessary. For CSV I think the required info is only the parity of quotes, though I could be wrong.

Re: Show HN: Parsing CSV files with GPU

#57

Post by TheLoneWolfling »

victorNicollet wrote: post #25

Very interesting. From my experience, the hard part about parsing CSV isn't to identify the individual cells, but rather parsing those cells afterwards (as numbers, dates, etc). What is the performance of those operations (e.g. parsing YYYY-MM-DD dates to Unix timestamps) when performed on the GPU ? My company actually picked another optimization strategy, by making the tokenization significantly longer, but it de-du…

Makes sense for low-entropy data. Though I can see that approach choking on some datasets. What happens if every entry has a GUID, for example?

May be better to do a best-effort deduplication instead of an exhaustive approach.

Re: Show HN: Parsing CSV files with GPU

#59

Post by victorNicollet »

TheLoneWolfling wrote: post #57
victorNicollet wrote: post #25

Very interesting. From my experience, the hard part about parsing CSV isn't to identify the individual cells, but rather parsing those cells afterwards (as numbers, dates, etc). What is the performance of those operations (e.g. parsing YYYY-MM-DD dates to Unix timestamps) when performed on the GPU ? My company actually picked another optimization strategy, by making the tokenization significantly longer, but it de-du…

Makes sense for low-entropy data. Though I can see that approach choking on some datasets. What happens if every entry has a GUID, for example? May be better to do a best-effort deduplication instead of an exhaustive approach.

At some point, we considered tweaking by dropping any strings longer than a certain length from the deduplication (it also helps with memory usage when streaming the data).

Our method makes most sense for many-to-many data (several orders per product, several orders per day), which happens to be the largest data sets we manipulate (by 3 orders of magnitude). I can certainly see situations where this would not be the case (e.g. web crawler logs).

Re: Show HN: Parsing CSV files with GPU

#60

Post by haberman »

pcwalton wrote: post #48
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…

> 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…

> (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.

I'm not able to access the full text of this paper. But from the description I wouldn't really consider this "parallel parsing." For the "skeleton parser" to be correct, it must transition through a state machine that is exactly as complex as the real parser. I suspect (again, not being able to read the paper right now) that what makes the "skeleton parse" faster than the "real parse" is not the speed of the parser itself, but the speed of the "load" on the parser.

For the skeleton parse, the "load" on the parser is just finding split points (cheap). At the application level, the "load" on the parser in many cases is building a tree of some sort. The tree-building is often significantly more expensive than the parse itself because it usually involves a lot of dynamic memory allocation.

So yes, if you do a preliminary parse that chunks up the document, and then a second parse that has a heavier load on it like tree-building, the second parse can indeed be parallelized. But I wouldn't consider this parallelizing a parser, I would consider it parallelizing the tree-building. In raw terms you have probably spent more CPU on the actual parsing logic than in the single-threaded case.

I don't mean for this to be a semantic quibble. I'm really interested in parsing architectures that decouple the parser itself from its "load." Event-based parsers like SAX parsers do this. I'm interested specifically in the parser part itself, and the limits of how it can be optimized.

> (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].

Looks like an interesting paper, I'll have to dig more into that.

Post reply on HN