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

What can you do in 2k LOC of C?

h4ck3r.net

Post reply on HN
Print view View original

101–110 of 110 posts

Re: What can you do in 2k LOC of C?

#101

Post by groby_b »

kragen wrote: post #92
haberman wrote: post #91

Earlier quoted context omitted.

> It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations For this speed-obsessed project, I wouldn't have it any other way: Benchmarking hash lookups in an integer-keyed hash table. Table size: 8, keys: 1-8 ==== upb_inttable(seq): 410 M/s upb_inttable(rand): 334 M/s std::map (seq): 149 M/s std::map (rand): 170 M/s __gnu_cxx::hash_map (seq…

Summarizing your results, your hash table implementation is between five and ten times faster than STL and G++ generic maps, because G++, like most C++ compilers, imposes a substantial abstraction penalty on the use of templates — even though in theory that's not necessary. Is that right?

See OP for hash_map. And std::map is dog slow because somebody thought a Red-Black-Tree is a good idea for a map.

So at least part of the penalty there is simply choosing the wrong data structure.

Also, IIRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations.

Re: What can you do in 2k LOC of C?

#102

Post by johne »

nostrademons wrote: post #33

In 2000 lines of C, you can encode the HTML5 "named character character entity" table. http://dev.w3.org/html5/spec/Overview.html#named-character-r... I hate HTML.

O.. M.. F.. G.. I had no idea they did this. I mean, what is the point? Talk about "not invented here" mentality: "I've got a fantastic idea! Unicode already has an official name for every Unicode character, so let's throw all of that out and come up with our own names that have no relation to what those Unicode guys did! And while we're at it, HTML4, HTML5? Version numbers are for pu$$7$s, so lets drop that too, and then randomly throw in a few hundred extra character entities every two to eighteen months for a fresh 'What's new' bullet point!"

Re: What can you do in 2k LOC of C?

#103

Post by nostrademons »

johne wrote: post #102
nostrademons wrote: post #33

In 2000 lines of C, you can encode the HTML5 "named character character entity" table. http://dev.w3.org/html5/spec/Overview.html#named-character-r... I hate HTML.

O.. M.. F.. G.. I had no idea they did this. I mean, what is the point? Talk about "not invented here" mentality: "I've got a fantastic idea! Unicode already has an official name for every Unicode character, so let's throw all of that out and come up with our own names that have no relation to what those Unicode guys did! And while we're at it, HTML4, HTML5? Version numbers are for pu$$7$s, so lets drop that too, and…

It's for backwards compatibility, like most of the HTML5 spec. If browsers suddenly start becoming HTML5-compliant and as a result most of the web stops working, then they've failed.

I agree with the reasoning. But damn, it makes things suck going forwards. This is why we can't have nice things. :-(

Re: What can you do in 2k LOC of C?

#104

Post by ajays »

silentbicycle wrote: post #3

I'm working on a text indexing/retrieval program, like locate ( http://www.openbsd.org/cgi-bin/man.cgi?query=locate ) but for content and not just filenames, and with an index It's very nearly together (integrating individually working parts now), and is currently ~1,500 lines (according to sloccount). Adding support for indexing Unicode text, more configuration, composite search queries (A and B near C and not D), e…

Does the index include the dictionary too, in your calculation? I'd be interested in seeing this indexing/retrieval program of yours, I hope you release it soon!

Re: What can you do in 2k LOC of C?

#105

Post by silentbicycle »

ajays wrote: post #104
silentbicycle wrote: post #3

I'm working on a text indexing/retrieval program, like locate ( http://www.openbsd.org/cgi-bin/man.cgi?query=locate ) but for content and not just filenames, and with an index It's very nearly together (integrating individually working parts now), and is currently ~1,500 lines (according to sloccount). Adding support for indexing Unicode text, more configuration, composite search queries (A and B near C and not D), e…

Does the index include the dictionary too, in your calculation? I'd be interested in seeing this indexing/retrieval program of yours, I hope you release it soon!

Yes.

Re: What can you do in 2k LOC of C?

#106

Post by haberman »

groby_b wrote: post #101
kragen wrote: post #92

Earlier quoted context omitted.

Summarizing your results, your hash table implementation is between five and ten times faster than STL and G++ generic maps, because G++, like most C++ compilers, imposes a substantial abstraction penalty on the use of templates — even though in theory that's not necessary. Is that right?

See OP for hash_map. And std::map is dog slow because somebody thought a Red-Black-Tree is a good idea for a map. So at least part of the penalty there is simply choosing the wrong data structure. Also, IIRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations.

> And std::map is dog slow because somebody thought a Red-Black-Tree is a good idea for a map.

What's wrong with red-black trees for an ordered map?

> IRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations.

This is absolutely an issue for insert performance, but I was only benchmarking lookup performance, which should not perform any allocations.

Re: What can you do in 2k LOC of C?

#107

Post by pnathan »

jpd wrote: post #26
pnathan wrote: post #17

I wrote an cooperative multitasking RTOS for an ATMega processor in 1200 or so lines.

If you're willing to share the code, I'm sure many of us would love to see it.

Here you go!

https://bitbucket.org/pnathan/uirtos

Turned out it was a preemptive RTOS. I had forgotten that.

Re: What can you do in 2k LOC of C?

#108

Post by cdavid »

gnaritas wrote: post #42
cdavid wrote: post #19

Earlier quoted context omitted.

This is also why we have many more softwares available now. The improvement in hardware specs are so useful not only because it is faster, but also because we can do much more without having to care about the details. Writing tiny, efficient libraries is cool, but it takes a lot of time, everything else being equal, so if you can afford not doing it, you don't.

> This is also why we have many more softwares available now. Assuming English isn't your first language, that would be phrased "much more software"; software is always singular.

Thanks for the correction (but I guess the correction still stand even if English were my first language).

Re: What can you do in 2k LOC of C?

#109

Post by kragen »

haberman wrote: post #106
groby_b wrote: post #101

Earlier quoted context omitted.

See OP for hash_map. And std::map is dog slow because somebody thought a Red-Black-Tree is a good idea for a map. So at least part of the penalty there is simply choosing the wrong data structure. Also, IIRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations.

> And std::map is dog slow because somebody thought a Red-Black-Tree is a good idea for a map. What's wrong with red-black trees for an ordered map? > IRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations. This is absolutely an issue for insert performance, but I was only benchmarking lookup performance, which should not perform any allocations.

> What's wrong with red-black trees for an ordered map?

I was wondering that too, except without the "n ordered" part. The claim that trees are competitive with hash tables in the average case rests on the claim that comparison is much faster than hashing, because you only have to hash once in the average case, whereas you have to compare something like 1.5 lg N times in the average case, which might be between 4 and 22 in common cases. I just ran this microbenchmark to compare hashing integers with comparing them, and hashing seems to be actually slightly faster than comparing on my CPU; this implies that hash tables should be dramatically faster than red-black trees.

https://gist.github.com/814746

In theory, this forces an unpleasant dilemma on code that aspires to be real-time but wants to do a lookup in a finite map: use hash tables with their awful worst-case performance (typically O(N), although you can improve this by hanging trees off your hash buckets, but that would be stupid), or use trees with their awful average-case performance?

In practice, I've never written real-time code, so I don't know if this dilemma is real.

Re: What can you do in 2k LOC of C?

#110

Post by groby_b »

haberman wrote: post #106
groby_b wrote: post #101

Earlier quoted context omitted.

See OP for hash_map. And std::map is dog slow because somebody thought a Red-Black-Tree is a good idea for a map. So at least part of the penalty there is simply choosing the wrong data structure. Also, IIRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations.

> And std::map is dog slow because somebody thought a Red-Black-Tree is a good idea for a map. What's wrong with red-black trees for an ordered map? > IRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations. This is absolutely an issue for insert performance, but I was only benchmarking lookup performance, which should not perform any allocations.

It won't perform allocations, but since the structure has been built from multiple disjoint allocations, you're likely to get worse spatial coherence. (I.e. more cache misses)

And yes, for an ordered map RBL is not a bad choice. "I object to std::map being ordered" would probably have been the better wording.

Post reply on HN