What can you do in 2k LOC of C? • Hacker News Board

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

#11

Post by haberman » Thu, Feb 03, 2011, 11:59 PM UTC

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 load others)

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

#12

Post by Zev » Fri, Feb 04, 2011, 12:02 AM UTC

An JSON / XML / YAML parser?

The fastest JSON parser that I know of is implemented in ~1800 lines of Objective-C: https://github.com/johnezang/JSONKit. Its about 2-3x faster than the yajl bindings for Objective-C are, in my testing.

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

#13

Post by zephjc » Fri, Feb 04, 2011, 12:12 AM UTC

Write a basic Lisp interpreter/compiler and write everything else in Lisp? :)

Would compiling Lisp code count against the challenge's LOC limit?

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

#14

Post by joe_the_user » Fri, Feb 04, 2011, 12:25 AM UTC

The next question is:

How many of these 2K sections can you string together to make something of further use? (using another 2k section, of course)

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

#15

Post by abecedarius » Fri, Feb 04, 2011, 12:27 AM UTC

zephjc wrote: post #13

Write a basic Lisp interpreter/compiler and write everything else in Lisp? :) Would compiling Lisp code count against the challenge's LOC limit?

I did once write a 2k-line bytecode interpreter and runtime for R4RS Scheme -- the compiler, library, and debugger were another 2-3kloc of Scheme. I even used it as my main hacking platform for years. But I didn't post it here because:

* It depends on the Boehm garbage collector.

* (This is embarrassing.) It stopped working after some version bump of GCC, and the cause is not at all obvious to me. Since I don't Scheme much anymore I gave up.

http://wry.me/~darius/software/uts.tar.gz if anyone cares.

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

#16

Post by js2 » Fri, Feb 04, 2011, 1:19 AM UTC

  $ git show e83c5163316f89bfbde7d9ab23ca2e25604af290 --stat
  commit e83c5163316f89bfbde7d9ab23ca2e25604af290
  Author: Linus Torvalds 
  Date:   Thu Apr 7 15:13:13 2005 -0700

    Initial revision of "git", the information manager from hell

   Makefile       |   40 +++++++++
   README         |  168 ++++++++++++++++++++++++++++++++++++
   cache.h        |   93 ++++++++++++++++++++
   cat-file.c     |   23 +++++
   commit-tree.c  |  172 +++++++++++++++++++++++++++++++++++++
   init-db.c      |   51 +++++++++++
   read-cache.c   |  259 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   read-tree.c    |   43 +++++++++
   show-diff.c    |   81 ++++++++++++++++++
   update-cache.c |  248 +++++++++++++++++++++++++++++++++++++++++++++++++++++
   write-tree.c   |   66 ++++++++++++++
   11 files changed, 1244 insertions(+), 0 deletions(-)

:-)

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

#17

Post by pnathan » Fri, Feb 04, 2011, 1:44 AM UTC

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

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

#18

Post by derleth » Fri, Feb 04, 2011, 1:56 AM UTC

How much memory does the code the blog poster described leak? How does it respond to edge cases and invalid input? Finally, is it portable beyond one specific OS? Beyond POSIX or Windows-based systems?

Those questions are especially pertinent in C.

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

#19

Post by cdavid » Fri, Feb 04, 2011, 2:08 AM UTC

sliverstorm wrote: post #8

If you think about it for a second, you realize that TrueType rasterization can't be that hard because printers were doing it long ago on crappy little embedded processors, but the default is just to fall back on the big ugly library, and then wrap it and pretend it's not there. How about instead, just write some good code? This is why 'modern' software can still manage to bring a 3GHz quad-core to it's knees, IMHO

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.

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

#20

Post by jerf » Fri, Feb 04, 2011, 2:24 AM UTC

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't cover them you don't really have an XML parser, like CDATA handling, entity loading from a DTD, parsing DTDs at least well enough to get those entities, processor commands, etc. A useful subset certainly, something I'd actually call a real XML parser, I'm skeptical. Not quite ready to write the idea off, but skeptical. (It's saved from me writing if off entirely because if I read the spec correctly a parser is not required to resolve external DTD references, if it was it would be stick-a-fork-in-it done, you'd eat hundreds of lines just using raw sockets to do HTTP requests and manage them even halfway properly.)

A JSON parser? Heck yes, even with the UTF-8 handling. It wouldn't even necessarily suck.

[1]: http://www.w3.org/TR/REC-xml/#charsets