7 ms·

Ohhh, you wanna throw down eh? Hmmm. This would be a fun weekend project to reimplement XSV in Python and prove this wrong. :) Now, to make this a fair compari

by shawn 8y ago

Ohhh, you wanna throw down eh? Hmmm. This would be a fun weekend project to reimplement XSV in Python and prove this wrong. :) Now, to make this a fair comparison, are you excluding pypy? Or is that allowed for our game? How about LuaJIT or Node? Are those fair too?

sanderjd 8y ago
You should definitely do this. Personally, I strongly suspect you wouldn't prove him wrong if you did attempt this in any of the languages you mentioned. But if you're right and we're wrong, I'd love it! It would be great and eye-opening to dig into your implementation(s) to see how you pulled it off.
JoshTriplett 8y ago
> This would be a fun weekend project to reimplement XSV in Python and prove this wrong. I don't know as much about the internals or performance characteristics of XSV (though it certainly touts performance as a feature), but if you can reimplement ripgrep in Python and get anywhere close to the same performance, I'd certainly be interested to see that. > Now, to make this a fair comparison, are you excluding pypy? Or is that allowed for our game? PyPy is not available everywhere, unlike the CPython runtime or the ability to run compiled binaries.
burntsushi 8y ago
I would definitely love to be proven wrong, because if I am, I am certain I would learn something new. I am pretty comfortable with Python, so I am pretty comfortable saying that you could not write a tool as fast as xsv in Python without writing some substantial portion of it in C. Using Python's standard library CSV parser is certainly fair game, but writing more C code on top of that which included the loop over records in a CSV file feels like a cheat. The problem here is that you've already lost because xsv's CSV parser is faster than Python's parser at the C level[1]. :-) Assuming I haven't made any silly gaffes in xsv itself, I don't see how you're going to make up the difference. Because of that, I am willing to extend a handicap: if you can get within the same order of magnitude as xsv while doing the same amount of work in a robust way, then I think I might even learn something there too. :-) I am less certain about PyPy, LuaJIT or Node, but I am certain I'd learn something if you proved me wrong. Note that a problematic part of this challenge is that your program would need to correctly handle CSV in a robust manner. It is very easy to write a very fast CSV parser that doesn't correctly handle all of the corner cases. Python's CSV parser certainly passes that test, but I don't know if Node's or Lua's CSV parser does because I've never used them. [1] - https://github.com/BurntSushi/rust-csv/blob/master/csv-core/src/reader.rs https://github.com/BurntSushi/rust-csv/blob/master/csv-core/...
- shawn 8y ago
  rust-csv compiled and ran flawlessly. xsv had an error: https://github.com/BurntSushi/xsv/issues/139 https://github.com/BurntSushi/xsv/issues/139 Also loved this: // OMG I HATE BYTE STRING LITERALS SO MUCH. fn b(s: &str) -> &[u8] { s.as_bytes() } EDIT: Aha, it was user error. Brew had an old version of Rust installed.
- shawn 8y ago
  Initial results: A naive parser in LuaJIT of your xsv-stats example: > (do (set csv (load "reader.l")) (set plays ((get (require 'system) 'read-file) "data/nfl_all_plays_small.csv")) (set s ((get csv 'stream) plays)) nil) > (let t1 (seconds) (let read (get csv 'read) (while (read s))) (- (seconds) t1)) 0.80387997627258 i.e. it can parse the whole nfl_all_plays_small.csv dataset in 803ms. $ time xsv stats --everything data/nfl_all_plays_small.csv > /dev/null real 0m0.323s user 0m0.520s sys 0m0.064s The CSV parser thus far is 62 lines: https://gist.github.com/shawwn/4c7f7e93ccf2e241e17e82d353301485 https://gist.github.com/shawwn/4c7f7e93ccf2e241e17e82d353301... Obviously, this is a naive parser and doesn't handle the corner cases you mention. But it's a useful starting point. Current CSV reader tests: https://gist.github.com/shawwn/53c06cd30f29b064c1f6c66f7896f208 https://gist.github.com/shawwn/53c06cd30f29b064c1f6c66f7896f... Will have more results soon. :) For basic record counting, LuaJIT takes 36ms: > (let t1 (seconds) (select 2 ((get string 'gsub) plays "\n" "\n")) (- (seconds) t1)) 0.036473989486694 xsv can do it in 29ms: $ time xsv count data/nfl_all_plays_small.csv 10000 real 0m0.029s user 0m0.018s sys 0m0.007s EDIT: Down to 400ms to parse the dataset.
  - shawn 8y ago
    Ok, the `count` command is implemented. The code is 27 lines: https://gist.github.com/shawwn/e178e597cbf7f3682153e449f66335a0 https://gist.github.com/shawwn/e178e597cbf7f3682153e449f6633... Without indexing, LuaJIT is twice as fast as XSV for 2.6M rows: $ rm data/*.csv.idx $ time lumen count.l data/nfl_all_plays_huge.csv 2592975 real 0m1.583s user 0m1.237s sys 0m0.311s $ time xsv count data/nfl_all_plays_huge.csv 2592975 real 0m3.184s user 0m2.425s sys 0m0.553s With indexing, LuaJIT is within an order of magnitude: $ xsv index data/nfl_all_plays_huge.csv $ time xsv count data/nfl_all_plays_huge.csv 2592975 real 0m0.019s user 0m0.009s sys 0m0.007s $ time lumen count.l data/nfl_all_plays_huge.csv 2592975 real 0m0.184s user 0m0.083s sys 0m0.096s I'll be implementing test cases to ensure it's catching malformed data.
dagenix 8y ago
It's perfectly fine to say "this is an impressive project. I don't understand why it couldn't be done in Python. I would love for someonet to explain that to me. Thanks!" It is not necessary to dismissively declare that some substantial piece of work could be implemented better in just a weekend.
- shawn 8y ago
  $ files | narrow \.rs$ | narrow '!tests' | xargs cat | nlines 4251 It's 4k lines of Rust. Shedding the static typing nonsense will get rid of at least 25% of that. Writing it in Lumen will buy an extra 2x in productivity. And there's nothing to discover; the algorithms are right there, and my claim is that they will run nearly as fast in a non-statically-typed language. I don't think the weekend claim is that outrageous. You don't like putting on a show for a crowd? It's one of the funnest things.
  - JoshTriplett 8y ago
    First of all, take a look at Cargo.toml for the list of dependencies; repeat recursively. Projects like xsv and ripgrep are modular, with many components that others can and do reuse. Second, lines of code hardly gives any but the roughest idea of how hard something would be to write, and write well. Third, interesting that you're not counting the test cases; after all, if you're not doing any static typing, surely you'll want more tests... Fourth, hey, as long as you're getting rid of the "static typing nonsense" you might as well drop the error handling and comments while you're at it. More seriously, though, type signatures and similar are hardly a significant part of the lines of code of the average Rust program. But in any case, you've already seen the replies elsewhere in the thread inviting you to try if you feel confident you can do so. > You don't like putting on a show for a crowd? It's one of the funnest things. You're certainly showing the crowd something about yourself. Whether it's what you're intending is another question. If you want to write a replacement or alternative for a tool, especially as an exercise in learning something, by all means do; it's a fun pastime. You don't need to dismiss someone else's work or choice of language in the process.
    - 8y ago
burntsushi 8y ago
Here's an example using csvkit: $ time xsv stats --everything /tmp/nfl_all_plays.csv > stats.csv real 5.723 user 14.390 sys 1.914 $ time csvstat /tmp/nfl_all_plays.csv ^C after 2.5 minutes Here's the data: https://burntsushi.net/stuff/nfl_all_plays.csv https://burntsushi.net/stuff/nfl_all_plays.csv It's only 74MB. Let's take a smaller slice to see how long csvstat really takes. This is just the first 10,000 records, which is ~3MB: https://burntsushi.net/stuff/nfl_all_plays_small.csv https://burntsushi.net/stuff/nfl_all_plays_small.csv $ time csvstat /tmp/nfl_all_plays_small.csv > /tmp/stats.csv real 1:01.85 user 1:01.70 sys 0.103 $ time xsv stats --everything /tmp/nfl_all_plays_small.csv > /tmp/stats.csv real 0.308 user 0.576 sys 0.071 Now technically, csvstat is doing more work in that it seems to be computing a frequency table as well. But we can just do the same for xsv and add the time, with the knowledge that it would be faster if it were coupled into `xsv stats`: $ time xsv frequency /tmp/nfl_all_plays_small.csv > /tmp/frequency.csv real 0.251 user 0.187 sys 0.063 Now let's see how xsv fairs on a much larger sample, which is just nfl_all_plays.csv repeated 10 times and is ~800MB: $ ls -lh /tmp/nfl_all_plays_huge.csv -rw-r--r-- 1 andrew users 806M Sep 8 20:34 /tmp/nfl_all_plays_huge.csv $ time xsv index /tmp/nfl_all_plays_huge.csv real 2.041 user 1.876 sys 0.163 $ time xsv stats --everything /tmp/nfl_all_plays_huge.csv > /tmp/stats.csv real 28.336 user 4:36.45 sys 24.212 $ time xsv frequency /tmp/nfl_all_plays_huge.csv > /tmp/frequency.csv real 6.077 user 1:16.51 sys 1.873 That indexing step lets xsv do its processing in parallel. Good luck doing that in Python without blowing your memory budget. :-) csvkit would either take hours to handle that much data or would more likely run out of memory. With that said, I was able to write a Python program that just counted records within an order of magnitude of `xsv count`, but it was still a few times slower.
- shawn 8y ago
  Mm, using someone else's parser would defeat the spirit of the challenge. I think xsv is worthwhile for being a robust parser, not necessarily for its performance. And my claim is that you'd be able to write it faster, without trading any security guarantees, in Lua, without sacrificing much performance. There's that pesky word, "much" performance. And that's really the interesting part here. How much would you trade away by shedding Rust? My hypothesis is less than 50% additional overhead. Thanks for providing a dataset. I think LuaJIT will match these stats, and it's a good baseline to start with. But yes, the CSV parser is around 15k lines. That'd be the trickiest part.

by shawn 8y ago

sanderjd 8y ago

You should definitely do this. Personally, I strongly suspect you wouldn't prove him wrong if you did attempt this in any of the languages you mentioned. But if you're right and we're wrong, I'd love it! It would be great and eye-opening to dig into your implementation(s) to see how you pulled it off.

JoshTriplett 8y ago

> This would be a fun weekend project to reimplement XSV in Python and prove this wrong. I don't know as much about the internals or performance characteristics of XSV (though it certainly touts performance as a feature), but if you can reimplement ripgrep in Python and get anywhere close to the same performance, I'd certainly be interested to see that. > Now, to make this a fair comparison, are you excluding pypy? Or is that allowed for our game? PyPy is not available everywhere, unlike the CPython runtime or the ability to run compiled binaries.

burntsushi 8y ago

I would definitely love to be proven wrong, because if I am, I am certain I would learn something new. I am pretty comfortable with Python, so I am pretty comfortable saying that you could not write a tool as fast as xsv in Python without writing some substantial portion of it in C. Using Python's standard library CSV parser is certainly fair game, but writing more C code on top of that which included the loop over records in a CSV file feels like a cheat. The problem here is that you've already lost because xsv's CSV parser is faster than Python's parser at the C level[1]. :-) Assuming I haven't made any silly gaffes in xsv itself, I don't see how you're going to make up the difference. Because of that, I am willing to extend a handicap: if you can get within the same order of magnitude as xsv while doing the same amount of work in a robust way, then I think I might even learn something there too. :-) I am less certain about PyPy, LuaJIT or Node, but I am certain I'd learn something if you proved me wrong. Note that a problematic part of this challenge is that your program would need to correctly handle CSV in a robust manner. It is very easy to write a very fast CSV parser that doesn't correctly handle all of the corner cases. Python's CSV parser certainly passes that test, but I don't know if Node's or Lua's CSV parser does because I've never used them. [1] - https://github.com/BurntSushi/rust-csv/blob/master/csv-core/src/reader.rs https://github.com/BurntSushi/rust-csv/blob/master/csv-core/...

shawn 8y ago
rust-csv compiled and ran flawlessly. xsv had an error: https://github.com/BurntSushi/xsv/issues/139 https://github.com/BurntSushi/xsv/issues/139 Also loved this: // OMG I HATE BYTE STRING LITERALS SO MUCH. fn b(s: &str) -> &[u8] { s.as_bytes() } EDIT: Aha, it was user error. Brew had an old version of Rust installed.
shawn 8y ago
Initial results: A naive parser in LuaJIT of your xsv-stats example: > (do (set csv (load "reader.l")) (set plays ((get (require 'system) 'read-file) "data/nfl_all_plays_small.csv")) (set s ((get csv 'stream) plays)) nil) > (let t1 (seconds) (let read (get csv 'read) (while (read s))) (- (seconds) t1)) 0.80387997627258 i.e. it can parse the whole nfl_all_plays_small.csv dataset in 803ms. $ time xsv stats --everything data/nfl_all_plays_small.csv > /dev/null real 0m0.323s user 0m0.520s sys 0m0.064s The CSV parser thus far is 62 lines: https://gist.github.com/shawwn/4c7f7e93ccf2e241e17e82d353301485 https://gist.github.com/shawwn/4c7f7e93ccf2e241e17e82d353301... Obviously, this is a naive parser and doesn't handle the corner cases you mention. But it's a useful starting point. Current CSV reader tests: https://gist.github.com/shawwn/53c06cd30f29b064c1f6c66f7896f208 https://gist.github.com/shawwn/53c06cd30f29b064c1f6c66f7896f... Will have more results soon. :) For basic record counting, LuaJIT takes 36ms: > (let t1 (seconds) (select 2 ((get string 'gsub) plays "\n" "\n")) (- (seconds) t1)) 0.036473989486694 xsv can do it in 29ms: $ time xsv count data/nfl_all_plays_small.csv 10000 real 0m0.029s user 0m0.018s sys 0m0.007s EDIT: Down to 400ms to parse the dataset.
- shawn 8y ago
  Ok, the `count` command is implemented. The code is 27 lines: https://gist.github.com/shawwn/e178e597cbf7f3682153e449f66335a0 https://gist.github.com/shawwn/e178e597cbf7f3682153e449f6633... Without indexing, LuaJIT is twice as fast as XSV for 2.6M rows: $ rm data/*.csv.idx $ time lumen count.l data/nfl_all_plays_huge.csv 2592975 real 0m1.583s user 0m1.237s sys 0m0.311s $ time xsv count data/nfl_all_plays_huge.csv 2592975 real 0m3.184s user 0m2.425s sys 0m0.553s With indexing, LuaJIT is within an order of magnitude: $ xsv index data/nfl_all_plays_huge.csv $ time xsv count data/nfl_all_plays_huge.csv 2592975 real 0m0.019s user 0m0.009s sys 0m0.007s $ time lumen count.l data/nfl_all_plays_huge.csv 2592975 real 0m0.184s user 0m0.083s sys 0m0.096s I'll be implementing test cases to ensure it's catching malformed data.

dagenix 8y ago

It's perfectly fine to say "this is an impressive project. I don't understand why it couldn't be done in Python. I would love for someonet to explain that to me. Thanks!" It is not necessary to dismissively declare that some substantial piece of work could be implemented better in just a weekend.

shawn 8y ago
$ files | narrow \.rs$ | narrow '!tests' | xargs cat | nlines 4251 It's 4k lines of Rust. Shedding the static typing nonsense will get rid of at least 25% of that. Writing it in Lumen will buy an extra 2x in productivity. And there's nothing to discover; the algorithms are right there, and my claim is that they will run nearly as fast in a non-statically-typed language. I don't think the weekend claim is that outrageous. You don't like putting on a show for a crowd? It's one of the funnest things.
- JoshTriplett 8y ago
  First of all, take a look at Cargo.toml for the list of dependencies; repeat recursively. Projects like xsv and ripgrep are modular, with many components that others can and do reuse. Second, lines of code hardly gives any but the roughest idea of how hard something would be to write, and write well. Third, interesting that you're not counting the test cases; after all, if you're not doing any static typing, surely you'll want more tests... Fourth, hey, as long as you're getting rid of the "static typing nonsense" you might as well drop the error handling and comments while you're at it. More seriously, though, type signatures and similar are hardly a significant part of the lines of code of the average Rust program. But in any case, you've already seen the replies elsewhere in the thread inviting you to try if you feel confident you can do so. > You don't like putting on a show for a crowd? It's one of the funnest things. You're certainly showing the crowd something about yourself. Whether it's what you're intending is another question. If you want to write a replacement or alternative for a tool, especially as an exercise in learning something, by all means do; it's a fun pastime. You don't need to dismiss someone else's work or choice of language in the process.
  - 8y ago

burntsushi 8y ago

Here's an example using csvkit: $ time xsv stats --everything /tmp/nfl_all_plays.csv > stats.csv real 5.723 user 14.390 sys 1.914 $ time csvstat /tmp/nfl_all_plays.csv ^C after 2.5 minutes Here's the data: https://burntsushi.net/stuff/nfl_all_plays.csv https://burntsushi.net/stuff/nfl_all_plays.csv It's only 74MB. Let's take a smaller slice to see how long csvstat really takes. This is just the first 10,000 records, which is ~3MB: https://burntsushi.net/stuff/nfl_all_plays_small.csv https://burntsushi.net/stuff/nfl_all_plays_small.csv $ time csvstat /tmp/nfl_all_plays_small.csv > /tmp/stats.csv real 1:01.85 user 1:01.70 sys 0.103 $ time xsv stats --everything /tmp/nfl_all_plays_small.csv > /tmp/stats.csv real 0.308 user 0.576 sys 0.071 Now technically, csvstat is doing more work in that it seems to be computing a frequency table as well. But we can just do the same for xsv and add the time, with the knowledge that it would be faster if it were coupled into `xsv stats`: $ time xsv frequency /tmp/nfl_all_plays_small.csv > /tmp/frequency.csv real 0.251 user 0.187 sys 0.063 Now let's see how xsv fairs on a much larger sample, which is just nfl_all_plays.csv repeated 10 times and is ~800MB: $ ls -lh /tmp/nfl_all_plays_huge.csv -rw-r--r-- 1 andrew users 806M Sep 8 20:34 /tmp/nfl_all_plays_huge.csv $ time xsv index /tmp/nfl_all_plays_huge.csv real 2.041 user 1.876 sys 0.163 $ time xsv stats --everything /tmp/nfl_all_plays_huge.csv > /tmp/stats.csv real 28.336 user 4:36.45 sys 24.212 $ time xsv frequency /tmp/nfl_all_plays_huge.csv > /tmp/frequency.csv real 6.077 user 1:16.51 sys 1.873 That indexing step lets xsv do its processing in parallel. Good luck doing that in Python without blowing your memory budget. :-) csvkit would either take hours to handle that much data or would more likely run out of memory. With that said, I was able to write a Python program that just counted records within an order of magnitude of `xsv count`, but it was still a few times slower.

shawn 8y ago
Mm, using someone else's parser would defeat the spirit of the challenge. I think xsv is worthwhile for being a robust parser, not necessarily for its performance. And my claim is that you'd be able to write it faster, without trading any security guarantees, in Lua, without sacrificing much performance. There's that pesky word, "much" performance. And that's really the interesting part here. How much would you trade away by shedding Rust? My hypothesis is less than 50% additional overhead. Thanks for providing a dataset. I think LuaJIT will match these stats, and it's a good baseline to start with. But yes, the CSV parser is around 15k lines. That'd be the trickiest part.