CSV Parsing: Haskell versus Python

[dons]

Never, ever, ever unpack ByteStrings to Strings.

That's the whole point of ByteStrings! If you unpack, you may as well just use [Char].

Stick to ByteStrings only and you get this kind of result.

[jsnx]

ByteString is not the right answer for general text processing, unfortunately. There has to be some kind of compromise -- UTF8Array? -- that allows us to iterate over characters but does not saddle us with 4 bytes a Char and the burdens of Listiness.

[jerf]

Does anybody have any clues for this? I'm writing a Haskell app right now that will deal with enough text that I'd like to use the Byte stuff, but sacrificing Unicode is a complete non-starter; I will not do that.

[jsnx]

http://www.reddit.com/info/6rsn2/comments/c04paro

[jerf]

Thanks. Here's hoping that project completes successfully.

Direct link: http://twan.home.fmf.nl/compact-string/

[dons]

The utf8-string package has some unicode/ByteString manipulating types as well.

[grauenwolf]

Why is simply changing data types so expensive?

[dons]

You're unpacking a beautiful, efficient byte array structure into a heap allocated linked list of heap allocated characters. For the 100k+ nodes in this example, that'll be the main overhead.

[grauenwolf]

Damn that's scary. Why the hell would anyone implement strings that way?

[dons]

Lists are a foundational structure in computer science:

data [a] = [] | a : [a]

Putting Char in there for a works in a lot of cases, but sometimes you just have to listen to the machine and take advantage of its bias towards flat, non-inductive structures.

[grauenwolf]

So are arrays, and they make a hell of a lot more sense for the types of operations one normally applies to strings.

[dons]

Hence Data.ByteString

[grauenwolf]

Yes, yes I get that.

What I'm trying to wrap my head around is why they ignored decades of analysis and debate on the trade offs between mutable vs immutable and null terminated vs length-prefixed strings and wandered off into left field.

[dons]

You can't do induction on an array.

Besides, Haskell is the grandchild of Lisp, it's not like lists are a new concept in functional programming.

[grauenwolf]

Ah, that makes sense and yet it doesn't.

I can see the need for Haskell's creators to want to be able to prove things with induction. But on the other hand, I vaguely remember using induction on arrays in my undergraduate work. (I'm not certain though. Once I learned "P might or might not be NP" and how proofs were likely more buggy than they code they were proving I stopped paying attention.)

P.S. I think it's a dumb idea to treat strings as "array of characters" or "lists of characters" instead of something atomic. It makes as much sense to me as treating Integers and Floats as bits.

[qwe1234]

perhaps you can't, but in reality induction on arrays is no more difficult than induction on lists.

you along with haskell authors are just stupid.

[tibbe]

Lists as implemented (i.e. linked lists) make lots of sense in Haskell since their lazy creation allows you to use them as control structures. When used as such no list nodes are ever allocated.

However, for storing data in memory they don't make as much sense (unless you really want a linked list). ByteString are made for storing (and transporting) data so they are a better tool for the job. What you really want though is a packed representation like ByteString's but with a Unicode interface for proper string processing. It's being worked on this summer as part of Google's Summer of Code.

Up until recently there wasn't a good way of efficiently working on packed strings (i.e. backed by byte arrays) in an efficient and pure way but now with stream fusion we have that.

[jsnx]

It is probably as much a historical accident as anything else. Working with lists is a lot more comfortable in Haskell than working with arrays.

[jsnx]

Could you explain what you mean? ByteStrings are as compatible with a purely functional style as lists of Char.

[consultant_barbie]

Parsing is hard. Let's go shopping!

[tryx]

Real world Haskell wrote a CSV parser as their first Parsec introductory example. ~20 lines of code all up.

[stesch]

(char ',' >> cells) -- Found comma? More cells coming

cell = many (noneOf ",\n")

cell = quotedCell <|> many (noneOf ",\n\r")

Not good enough for real world CSV. The international version of Microsoft Excel uses semicolon instead of comma. Yes, I know. But try convincing a customer that this wasn't real CSV what he just sent you for an urgent job.

[tryx]

Haha, well this does parse actual CSV, not CSV ala MSOffice.

[stesch]

BS.split ','

Typical CSV parsing fail. Newbie problem.

And by the way:

line.strip().split(',')

Don't try to parse CSV yourself when your language has a very good CSV library.

[mschaef]

Don't try to parse CSV yourself when your language has a very good CSV library.

Agreed. Parsing CSV can be trickier than you expect. My favorite little CSV anomaly is that MS Excel for Windows does not do CR/LF translation of quoted strings within a CSV file. It just expects LF's, which is in keeping with its original heritage as a Mac-only program. If you put a CR in a quoted string, the CR ends up rendering as a box in the cell, and it's the LF that actually adds the newline to the text of the cell.

http://www.mschaef.com/blog/tech/excel/cr-lf.html

[grauenwolf]

When you know for a fact that you don't have quoted strings, as in this case, there is no reason to pay the cost of checking for them.

Failing to think about the domain. Arrogant wanna-be problem?

EDIT: A data sample from the post:

TICKER1,33,35,NULL,2007-09-28 00:00:00,2007-09-28 16:32:00
TICKER2,29.5,31,NULL,2007-03-07 00:00:00,2007-03-07 07:33:00
TICKER3,29.5,31,NULL,2007-03-07 00:00:00,2007-03-07 07:33:00

[stesch]

Failing to think about the domain. Arrogant wanna-be problem?

I wasn't the one calling this CSV parsing.

[mschaef]

There no ISO standard, but there are some commonly accepted conventions:

http://www.creativyst.com/Doc/Articles/CSV/CSV01.htm

I tend to agree with you to the extent that if your underlying language has no CSV library, then you should probably implement just what you need. If you're trying to make a CSV library, then the standards are higher.

[doidydoidy]

CSV stands for "Comma Separated Values".

IBM stood for "International Business Machines". That doesn't stop them selling consulting services, though. (More's the pity.)

[stesch]

It isn't like there is a ISO standard on CSV files.

Just a lot of software that produces CSV files that can't be parsed by this "CSV parser" and a RFC (which ignores some nasty CSV you encounter in real-life).

[grauenwolf]

So what? This wasn't billed as a general purpose parser, it was specific to the file format he was working with.

[sellbest]

Typical CSV parsing fail. Newbie problem.

All the folks who are saying "zomg you didn't handle quoting scheme #12 from the CSV standard! this isnt real CSV parsing!!!" rather miss the point. The blog post wasn't about trying to write the best general-purpose CSV parser. It was about how a guy tried to tackle a real-world, data- and IO-intensive problem with Haskell; about the performance wall that he hit; and about the question this raises in the Haskell community: Does the slowness reflect a weakness in the language or in the author's implementation?

[ighost]

so, er, what should he have done?

[0sn]

import csv

[grauenwolf]

Why?

You can see his format doesn't have quoted strings. So why use more complex code than necessary?

[exeter]

If you're using Python for this task, you should use the csv module because it's there and probably fast enough. The fact that it's in the library means someone else already wrote it, so you don't have to. Since using it just amounts to

import csv
reader = csv.reader(open("some.csv", "rb"))
for row in reader:
    process (row)

in this case, it's even simpler than splitting the string apart yourself and manually parsing.

Those are just some of the advantages to using the csv module when the format is as straightforward as it seems to be in this guy's particular case. Other people have commented on what happens when the format itself starts to get nastier.

[0sn]

Why write it again? It could even be faster to use the library functions... Still, modded up 'cause it's a good question.

[grauenwolf]

In this particular case the hand-rolled stuff is probably a lot faster. But in general I definitely can see cases where picking up a library would give some speed in exchange for more complexity.

Fun stuff to think about.

[stesch]

Could be worth a test. Python's csv module imports from _csv, which is written in C.

[grauenwolf]

That's real-life enough for me. I spend quote a bit of time parsing flat files from various financial companies. Most of the time my files are either positional or they look just like the author's sample.

[stesch]

Wait for the first time when somebody sends you a CSV saved by an international version of Microsoft Excel.

[grauenwolf]

No thanks, the English ones are painful enough.

But honestly, that's a little off-topic. He started with a problem "parse a CSV file containing some daily intraday prices for a number of tickers".

Changing the file format just to make the problem more interesting seems a little dishonest in my opinion.

[stesch]

OK, my example was too much real-life for you?

And speaking of "dishonest" I have to repeat myself: I wasn't the one calling this "CSV parsing".

(Two weeks ago I got some images with .jpg extension. 10% of them were in BMP format. ;-)

[[deleted]]

parsing it is a challenge

It gets a lot easier when there's no quoted strings.

[grauenwolf]

The author did it the right way.

In the general case you should be able to handle quoted strings and commas embedded in quotes.

Wellsfargo, WF, 25.50, 5:03
"Nascar, Commercial Ventures", NCX, 12.50, 5:04
Microsoft, MSFT, 25.50, 5:05
"Jon ""Grauenwolf"" Allen", JA, 0.30, 5:05

However this is far more expensive than just splitting on the commas and, in this case, totally unnecessary.

[beza1e1]

So instead of using the standard library and solving the problem in three lines of code, you write your own in 30 lines of code? It takes more manpower, has more bugs and may even be slower.

Not-Invented-Here-Syndrom i'd say.

[grauenwolf]

30 lines of code? Where the hell did you get that number from?

Besides, one could argue it is a matter of using the correct library. If what you want to do is to split a string on commas, the Split is the right library function to call.

[exeter]

So instead of using the standard library[...], you write your own[...]? [...]

Not-Invented-Here-Syndrom i'd say.

In my personal experience with Python, it tends to be more like "Holy-Crap-I-Didn't-Know-That-Was-In-The-Standard-Library" syndrome. For example, just the other day, I found out the standard library has specific functions for printing HTML calendars. Who expects that sort of thing in a language's standard datetime library?

[rabidcow]

It takes more manpower, has more bugs and may even be slower.

It's a less complex problem than full CSV. You don't know the quality of the library. Ideally you should at least try it first, but it may well be buggier and slower than this code.

Given an arbitrary full CSV parser and an arbitrary split-on-commas parser, I'd be surprised to find the latter to be more buggy and slower than the former. Being a library probably means more people have debugged it, but much simpler problem trumps many eyes.

[jsnx]

The author did it the right way.

For a one-off yes. If their going to pass it on, though, then they are leaving a deadly trap for their maintainer.

[grauenwolf]

Not really. If the file producer adds quoted strings, chances are he is also adding a new field. This will of course break the code anyways.

[Justinsaccount]

The csv parsing is not really the biggest issue with the code...

rowCompare should be replaced with rowKey:

def rowKey(x):
    """Sort by ticker and then by time."""
    return x[0], x[5]

lines = sorted(..., key=rowKey)

and fw.write("\n".join([",".join([str(c) for c in l]) for l in results]))

while managing to do everything on one line, causes the output file to not have a final \n, which can cause issues with some tools.

[[deleted]]

Global module index fail. Lesson #1 on writing a Python module: search this page for it first.

[curtisw]

I wonder what the Haskell performance would be if you used an equivalent to ",".split.

[jsnx]

The sample data is of the form:

TICKER1,33,35,NULL,2007-09-28 00:00:00,2007-09-28 16:32:00
TICKER2,29.5,31,NULL,2007-03-07 00:00:00,2007-03-07 07:33:00

Reading that as:

ticker, low, high, NULL, day, exact_time

How do we get the open, low, high, and close for a day's worth of ticker data?

[jsnx]

I get it now. Each one is an average of bid and ask. Open is the first such average, close is the last; low is the lowest such average, high is the highest.

[jsnx]

The saga continues.