Live data from Hacker News

15-line hash table in C

pastes.archbsd.net

61–70 of 104 posts

Re: 15-line hash table in C

#61
post #2

This code reminds me why clever is the enemy of good.

Exactly. Why people try to write code in less lines of code? More lines == better readability, better debugging, easier to move around, easier to fix single parts and so on.

I do not code much, but I have to read a lot of code when I investigate bugs. I never see very concise code, but I have quite often verbose code. The readability of verbose code is very bad: I have to scroll a lot more to understand algorithm and often, it is split in many files.

In my experience more lines == reduced readability, more difficult to move around, more difficult to fix single parts (any change requires to modify many files) and so on. More lines of code is often against the simplicity.

I have seen code that was very difficult to understand. Rewriting it to make it simple never needed to increase the number of lines.

Re: 15-line hash table in C

#62
post #58

Earlier quoted context omitted.

A wasteful struct - are you kidding?

I'm not. Is there some performance penalty for using a struct over a 2 element array?

No performance penalty. It would make the code longer.

Consider " in lines" type articles to be performance pieces - the point is to make it short, not readable or user friendly.

Re: 15-line hash table in C

#63
post #58

Earlier quoted context omitted.

A wasteful struct - are you kidding?

I'm not. Is there some performance penalty for using a struct over a 2 element array?

In this case, it makes no difference. The array is used instead of a struct to save a few lines of code and making the title of this post more impressive.

Re: 15-line hash table in C

#64

Earlier quoted context omitted.

And an extra local variable. Which might take up a line of source code!

With two additional casts you can make it compile[1] as C++ - without the incredibly wasteful extra local variable. [1] http://codepad.org/

Your link to "http://codepad.org/" doesn't show any code. Did you forget some arguments in the URL?

Re: 15-line hash table in C

#65
post #61

Earlier quoted context omitted.

Exactly. Why people try to write code in less lines of code? More lines == better readability, better debugging, easier to move around, easier to fix single parts and so on.

I do not code much, but I have to read a lot of code when I investigate bugs. I never see very concise code, but I have quite often verbose code. The readability of verbose code is very bad: I have to scroll a lot more to understand algorithm and often, it is split in many files. In my experience more lines == reduced readability, more difficult to move around, more difficult to fix single parts (any change requires…

I agree in that I'd much rather read terse expressive code than pages of dribble convey anything meaningful, having seen a lot of verbose code too. That said, code should be well formed. When I started out in C I only used curly braces when I needed to. After creating several bugs stemming from this I now add them as a rule of thumb. That particular issue is compounded here by the fact that multiple statements are shoved on a single line - also poor form.

Re: 15-line hash table in C

#66
post #61

Earlier quoted context omitted.

Exactly. Why people try to write code in less lines of code? More lines == better readability, better debugging, easier to move around, easier to fix single parts and so on.

I do not code much, but I have to read a lot of code when I investigate bugs. I never see very concise code, but I have quite often verbose code. The readability of verbose code is very bad: I have to scroll a lot more to understand algorithm and often, it is split in many files. In my experience more lines == reduced readability, more difficult to move around, more difficult to fix single parts (any change requires…

I think it's a matter of balance - at one extreme is IOCCC-style excessive terseness+obfuscation, and at the other extreme is the type of excessively indirect code often referred to as "enterprisey". The average probably varies depending on the culture of the language (contrast the typical C project with a Java one, for example), but over the years I've found that as my skill with a language improves, my code tends to become more concise.

Whenever someone brings up the "cleverness" argument I always like to mention this counterpoint: http://www.linusakesson.net/programming/kernighans-lever/

Re: 15-line hash table in C

#67
post #9
post #4

will need the clockwise spiral rule to parse this: http://c-faq.com/decl/spiral.anderson.html

The author helpfully explains the code by way of un-optimizing it to something readable: http://pastes.archbsd.net/graphitemaster/hashtable_explinati...

That un-optimized version also helpfully lacks the buffer overflow bug.

Re: 15-line hash table in C

#68
post #2

This code reminds me why clever is the enemy of good.

Exactly. Why people try to write code in less lines of code? More lines == better readability, better debugging, easier to move around, easier to fix single parts and so on.

More lines == better readability, better debugging, easier to move around, easier to fix single parts and so on.

Disagree. There's a sweet spot. Code that is too dense (golfing code) is unreadable but so is code that's too long. Long code can be readable if the substructure is evident, but it's usually not.

There are two issues that come to mind on this. One is that concise code usually requires strong familiarity with the language. For example, Haskell allows dense and readable code-- if you know Haskell. Same with Clojure (Lisp). I hate Java, but one thing I'll say for it and its sprawling code is that it's relatively easy to (superficially?) understand (with an IDE to jump around, because modest programs can be thousands of lines) with a mediocre knowledge of the language.

I'd say the same of research-level mathematics. If you're intimately familiar with linear algebra notation and terminology because you use it every day, it's concise and readable. If not, then "(X^TX)^(-1)Xy" looks like line noise.

The second issue is that what tends to make large codebases unreadable is a failure of factoring. It's not that it's 500 lines* that is the problem, because the intrinsic complexity of the problem may be at a level where 400-500 lines is appropriate. It's when you have 500 lines in one class (ultimately, "class" and "object" are poorly-defined and that's why so much OOP code is trash) or, worse yet, one function/method (method is just a code-name for "locally interpreted stateful function") that you get hell code. This happens a lot in large imperative codebases (typically not becoming intractable until you have two or more programmers on the same code) because, in imperative code where an action (as opposed to stateless function) is the fundamental unit, things appear to compose better than they actually do.

In other words, it's complicated. In general, there seems to be a density level that accurately represents the intrinsic complexity of the problem. Go denser and you're forcing people to think in a specific (and poorly communicated) way to understand the implicit structure and policies that informed the code construction. On the other hand, typical sprawling Java code is great for testing your IDE's scrolling feature but the amount that can fit on a single page is low, and if this is coupled with long methods and huge classes, you get OOP (here, meaning "business OOP", not "Alan Kay's vision of OOP") spaghetti code.

Re: 15-line hash table in C

#69

For those of us who actually ship code, I'd like to suggest khash[1], which is a pretty nice implementation of a hash table in C. It uses lot's of macros, so if you're looking for a brain teaser you will be satisfied as well :) [1]: http://attractivechaos.github.io/klib/#Khash%3A%20generic%20...

uthash[1] is another good solution. It's pretty bulletproof and has lots of options. Also implemented with macros, if that's a plus :-). [1]: http://troydhanson.github.io/uthash/

I don't think being implemented with macros is a plus. I've seen some friends use it and get stuck whenever it was failing because it's impossible to know how it's working. It's the same type of cleverness some people criticize in other comments. Yes, it may be complete and useful but it's opaque.

Re: 15-line hash table in C

#70
Why the hell does this thing get upvoted ? What's good about this implementation? It's cryptic, it's buggy and it's useless for any practical purpose.

Why is this better than an array of structs ? How much longer can that be ?

Post reply on HN