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

81–90 of 110 posts

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

#81

Post by beagle3 »

silentbicycle wrote: post #32
pygy_ wrote: post #9

Roberto Ierusalimschy's lpeg is around 2.4k loc of ansi C without any dependency beside libC and lua.h (needed to interface with Lua, since it's a Lua library). It implements an efficient pattern matching system based on Parsing Expression Grammars (akin to CFGs, but without ambiguities). It consists of a Pattern/Grammar to bytecode compiler and a custom VM to interpret the result of the compiling phase. Nice and cle…

The Lua code itself (while not Also, in my experience, LPEG is a great fit for middle-ground parsing - more complex than Perlish regexps (which it handles well), and including those a bit more complex still, but it's awkward for really complex parsing (since it inherently combines lexing and parsing). But I dissed Perl and Tcl, so -1. Screw useful information. ;)

> but it's awkward for really complex parsing (since it inherently combines lexing and parsing).

I'm kind of surprised by that statement - grammars for programming languages expressed in PEG always seem much cleaner to me than the lex/parse separation. Can you give an example of a grammar that you find is complicated by PEG?

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

#82

Post by beagle3 »

silentbicycle wrote: post #35
haberman wrote: post #11

The core of my protobuf-decoding library upb ( https://github.com/haberman/upb/wiki ) is 3k SLOC of C. That includes * a hash table implementation * a reference-counted string type * a generic interface for doing tree traversals of protobuf data * the protobuf decoder itself (which implements the previous interface) * all the code to load proto descriptors (including bootstrapping the first one, which is necessary to…

It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations, atoms ("a reference-counted string type"), etc. When working with C, it sometimes makes sense to have bespoke data structures, but it always makes me think of Hanson's _C Interfaces and Implementations_, Greenspun's tenth rule, etc. My 1500loc C project also has a hash table implemen…

> It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations, atoms ("a reference-counted string type"), etc.

Well, the only reason for that is that C never had a hash table in its standard library. The same assertion is true about any other programming language I've seen that doesn't.

Python's and Lua's dicts are really hard to top (at least in the general case, and definitely inside the language), so there aren't even any attempts. Java's is slow and horrible, so there are hundreds of replacements, but they're all interface compatible.

> That and serializing custom data structures to disk accounts for more than half of its code.

That's one of the the things K gets unbelievably right - there is one routine (which with Arthur's style is probably 10 lines of C) for serialize, and another for deserialize. They work for any K structure, and they do that with blinding speed thanks to being totally memory mapped. My C code has switched to that approach as well - and it works really, really well.

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

#83

Post by silentbicycle »

kenjackson wrote: post #74
sofuture wrote: post #63

Earlier quoted context omitted.

I'd love to hear why that code doesn't embody brevity? As for obfuscation, it's rather straightforward -- it's just concise . A lack of instant understanding doesn't indicate that a piece of code is without merit, or not honest and straightforward.

To be clear. If someone submitted this code to you for code review you'd say, "nice and concise -- approved"? Really? I get this person may have been working with constraints we don't know about, but its not straightforward. Give this to 10 working C devs and ask them to tell you what it does without running it. The standard cues of straightforward code aren't there -- well named variables, well named functions, comm…

If we were working in an APL dialect, I would expect code like that. I can tell you what every token in that code is for, by the way. If we were working in C, no. But if you're trying to get C programmers to grok APL style, it's a good start.

The APL people are not fooling around, either - look at Kx's customers: http://kx.com/Customers/end-user-customers.php . And then check how much a license for kdb+ costs per core. Oh, and "a standard purchase requires licensing at least 8 cores."

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

#84

Post by silentbicycle »

beagle3 wrote: post #82
silentbicycle wrote: post #35

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, atoms ("a reference-counted string type"), etc. When working with C, it sometimes makes sense to have bespoke data structures, but it always makes me think of Hanson's _C Interfaces and Implementations_, Greenspun's tenth rule, etc. My 1500loc C project also has a hash table implemen…

> It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations, atoms ("a reference-counted string type"), etc. Well, the only reason for that is that C never had a hash table in its standard library. The same assertion is true about any other programming language I've seen that doesn't. Python's and Lua's dicts are really hard to top (at least…

My text indexer is using a mmap'd hash table too, and that's exactly why. :)

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

#85

Post by kenjackson »

silentbicycle wrote: post #83
kenjackson wrote: post #74

Earlier quoted context omitted.

To be clear. If someone submitted this code to you for code review you'd say, "nice and concise -- approved"? Really? I get this person may have been working with constraints we don't know about, but its not straightforward. Give this to 10 working C devs and ask them to tell you what it does without running it. The standard cues of straightforward code aren't there -- well named variables, well named functions, comm…

If we were working in an APL dialect, I would expect code like that. I can tell you what every token in that code is for, by the way. If we were working in C, no. But if you're trying to get C programmers to grok APL style, it's a good start. The APL people are not fooling around, either - look at Kx's customers: http://kx.com/Customers/end-user-customers.php . And then check how much a license for kdb+ costs per cor…

Honestly, I think your superhuman then. For the most part I don't think ANY programming language is understandable without well named "tokens".

I'm curious, do you think you could tell me what some arbitrary C code does that I give you, where I've changed all the variables to "a", "b", "c", etc...? I'd be hardpressed to believe anyone in the world could.

Is APL structurally so expressive that huamns can easily extract meaning from structure? If so this is the single great accomplishment in the history of computer science. This dwarfs any contribution from Lisp, C, FORTRAN, theory of computation, etc...

And the fact that I know some of the people that worked on the original versions of APL at IBM, yet they never mentioned this, makes me suspect.

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

#86

Post by silentbicycle »

kenjackson wrote: post #85
silentbicycle wrote: post #83

Earlier quoted context omitted.

If we were working in an APL dialect, I would expect code like that. I can tell you what every token in that code is for, by the way. If we were working in C, no. But if you're trying to get C programmers to grok APL style, it's a good start. The APL people are not fooling around, either - look at Kx's customers: http://kx.com/Customers/end-user-customers.php . And then check how much a license for kdb+ costs per cor…

Honestly, I think your superhuman then. For the most part I don't think ANY programming language is understandable without well named "tokens". I'm curious, do you think you could tell me what some arbitrary C code does that I give you, where I've changed all the variables to "a", "b", "c", etc...? I'd be hardpressed to believe anyone in the world could. Is APL structurally so expressive that huamns can easily extrac…

> I'm curious, do you think you could tell me what some arbitrary C code does that I give you, where I've changed all the variables to "a", "b", "c", etc...? I'd be hardpressed to believe anyone in the world could.

If you know the specific context ahead of time (a FSM for lexing, a hash table implementation, etc), then it really isn't that hard.* Are you honestly telling me that you wouldn't be able to figure out how a hash table implementation worked if all the types and variable names were changed to single letters? It would slow you down, sure, but it wouldn't be impossible.

* Speaking as someone who has debugged code with variable names and comments in Swedish.

That code was written with the context of, "Hey, we both know APL really well, here's a quick prototype for a new implementation of it, could you give it a look?" When somebody is showing a Scheme implementation to other Lispers, they don't need to spend time explaining what a cdr is. Context matters.

Most of the functions in that take one or two arbitrarily-dimensioned arrays and loop simple operations over them. Everything takes (w) or (a, w) and returns z. i is a loop index (as usual). w->p is the array of values in w, ga allocates a new array. ("get array"? "generic allocate?")

   V1(iota){I n=*w->p;A z=ga(0,1,&n);DO(n,z->p[i]=i);R z;}
iota (the term comes from APL; J uses "i.", K uses "!", Q uses "til") takes a number and returns a vector of integers from 0 to n. iota 5 -> 0 1 2 3 4. Most of the definitions are equally simple, there just isn't much whitespace. DO is a macro that abstracts out the common "for (i=0; i<n; i++) { ... }" loop, which is used all over the place.

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

#87

Post by silentbicycle »

beagle3 wrote: post #81
silentbicycle wrote: post #32

Earlier quoted context omitted.

The Lua code itself (while not Also, in my experience, LPEG is a great fit for middle-ground parsing - more complex than Perlish regexps (which it handles well), and including those a bit more complex still, but it's awkward for really complex parsing (since it inherently combines lexing and parsing). But I dissed Perl and Tcl, so -1. Screw useful information. ;)

> but it's awkward for really complex parsing (since it inherently combines lexing and parsing). I'm kind of surprised by that statement - grammars for programming languages expressed in PEG always seem much cleaner to me than the lex/parse separation. Can you give an example of a grammar that you find is complicated by PEG?

I initially wrote the parser for a (proprietary) query language compiler using LPEG, and keeping track of lexical issues (whitespace, etc.) along with the grammatical structure complicated things. When I broke it apart and wrote a quick FSM-based lexer and a recursive descent parser, it became much simpler. Perhaps I could have factored the PEG grammar better, but with every PEG grammar I've had grow beyond a certain point, I've wished I could separate the lexing and parsing stages.

I much prefer working with LPEG to regular expressions for small to midsized stuff, though.

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

#88

Post by drobilla »

jerf wrote: post #20

Getting a standards-compliant XML parser into 2K lines is going to be a challenge, if you're not going to cheat on what a "line" is. You must be able to deal with both UTF-8 and UTF-16 [1] (and remember UTF-16 can be in either endian order), you have several tables of things like what chars are valid where, you've got data structures to declare, and there's a lot of edge cases that may not leap to mind but if you don…

I recently wrote a Turtle[1] parser and abbreviating serialiser[2] in just over 2K lines, which I'd say is roughly equivalent in complexity to doing the same for JSON. This is with UTF-8 support, full conformance, URI parsing/resolution, line/column error reporting, etc. A more kludgy job could be quite a bit smaller still...

[1]: http://www.w3.org/TeamSubmission/turtle/ [2]: http://drobilla.net/software/serd/

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

#89

Post by kenjackson »

silentbicycle wrote: post #86
kenjackson wrote: post #85

Earlier quoted context omitted.

Honestly, I think your superhuman then. For the most part I don't think ANY programming language is understandable without well named "tokens". I'm curious, do you think you could tell me what some arbitrary C code does that I give you, where I've changed all the variables to "a", "b", "c", etc...? I'd be hardpressed to believe anyone in the world could. Is APL structurally so expressive that huamns can easily extrac…

> I'm curious, do you think you could tell me what some arbitrary C code does that I give you, where I've changed all the variables to "a", "b", "c", etc...? I'd be hardpressed to believe anyone in the world could. If you know the specific context ahead of time (a FSM for lexing, a hash table implementation, etc), then it really isn't that hard.* Are you honestly telling me that you wouldn't be able to figure out how…

Are you honestly telling me that you wouldn't be able to figure out how a hash table implementation worked if all the types and variable names were changed to single letters?

Yes, probably not. I've looked at code that I've personally written with variable names -- in the debugger and still scratched my head trying to figure out what I had done. And not trying to overstate my ability, but I tend to be someone who is generally pretty good at reading code.

Here's some code you might run across in some DSP code. There are some globals, and hopefully I translated it correctly. But in any case, w/ good function variable naming I could understand the intent in a few seconds. Without it, I think I'd scratch my head for some time. How long does it take you to figure out what it does (or what it is intended to do)?

   ov f(){
   xx b, hh, i, pp, j, jj = PL, k;
   xx D = NN>>2*b,d=n-2*zz;
   t *z[B]; t *p, m, n, q, oo;
   for (i=0; i

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

#90

Post by silentbicycle »

kenjackson wrote: post #89
silentbicycle wrote: post #86

Earlier quoted context omitted.

> I'm curious, do you think you could tell me what some arbitrary C code does that I give you, where I've changed all the variables to "a", "b", "c", etc...? I'd be hardpressed to believe anyone in the world could. If you know the specific context ahead of time (a FSM for lexing, a hash table implementation, etc), then it really isn't that hard.* Are you honestly telling me that you wouldn't be able to figure out how…

Are you honestly telling me that you wouldn't be able to figure out how a hash table implementation worked if all the types and variable names were changed to single letters? Yes, probably not. I've looked at code that I've personally written with variable names -- in the debugger and still scratched my head trying to figure out what I had done. And not trying to overstate my ability, but I tend to be someone who is…

I think we're arguing past each other. The J prototype took me part of a morning to figure out (and get working on more modern hardware), but I wasn't familiar with APL conventions at the time. Code like that is slower to read, just not impossible.

About your code sample - I haven't done anything with digital signal processing code, so I couldn't tell you. It looks like some sort of wave transformation, but that's like saying code from a 3D rendering engine is "doing something with triangles", sorry.

Most of the APL functions are only a line or two long, though - that makes a big difference. "accumulate i..N", "get new vector with a[i] + w[i]", etc. The only part that is individually complex is the parser.

Post reply on HN