10 ms·

Shortly before Linus wrote this article in 2002, I wrote an XML-RPC library in C that used reference counting. By the time I was done, I'd written 7,000+ lines

by ekidd 16y ago

Shortly before Linus wrote this article in 2002, I wrote an XML-RPC library in C that used reference counting. By the time I was done, I'd written 7,000+ lines of extremely paranoid C code, and probably eliminated all the memory leaks. The project cost my client ~$5K. The standard Python xmlrpc library was less than 800 lines of code, and it was probably written in a day or two. Was my library about 50 times faster? Sure, I could parse 1,500+ XML-RPC requests/second. Did anybody actually benfit from this speed? Probably not. But the real problem is even bigger: Virtually every reference-counting codebase I've ever seen was full of bugs and memory leaks, especially in the error-handling code. I don't think more than 5% of programmers are disciplined enough to get it right. If I'm paying for the code, I'll prefer GC almost every time. I value correctness and low costs, and only worry about performance when there's a clear business need.

ekiru 16y ago
Linus suggested in the OP that automated reference counting (where the language implementation handles reference counting for the programmer) is preferable to GC. Python uses such reference counting (although it also has a GC fallback to ensure cyclic structures are collected).
- cdavid 16y ago
  And it is one of the reason why python is slow and difficult to scale on multiple cores (the main difficulty by far of removing the GIL is reference counting).
  - kragen 16y ago
    Scaling Python on multiple cores is easy: you just run multiple Python processes, each with its own per-core GIL. You are correct, though, that ref-counting overhead is one of the main reasons Python is slow.
    - cdavid 16y ago
      You are playing with words here: of course you can run multiple python instances to scale your application on multiple-cores, that's a trivial statement. But I was talking about python the interpreter (more exactly cpython). There are legitimate cases where multi-threading is the natural, elegant solution, and cpython, mostly because of reference counting, prevents that.
      - kragen 16y ago
        CPython prevents you from using shared-state multithreading to scale your application on multiple cores, but it doesn't prevent you from scaling your application on multiple cores. That's not "playing with words". It is indeed unfortunate when the limitations of our platforms force us to contort our code to improve performance, but that is just as true of multithreading as of multi-process programming. The difference between the complexity of the two is small.
    - gerner 16y ago
      Thank you for making this point. To my great dismay I see more and more people think that you need concurrent threads in one process in order to scale. It seems as if many programmers believe this as scripture and subsequently have difficulty thinking about distributed systems (not just multi-core, but multi-host).
    - SpikeGronim 16y ago
      The drawback with multiple processes is that they each have all the compiled bytecode on their heap. When I "import nltk" my heap goes from ~12 to ~36 MB. Add a few more dependencies and you end up wasting a non-trivial amount of RAM on python heaps.
      - lobster_johnson 16y ago
        You could do the import and then fork the child processes. That should share all the memory used by the nitk module between all the children (for as long as the memory is not modified by anyone, which triggers a copy-on-write allocation of the affected pages).
  - jrockway 16y ago
    C and Java apps with high contention don't scale well onto multiple cores, either. The key to speed is to not share state, which Python can do fine. It's called fork.
    - cdavid 16y ago
      Sometimes you cannot easily not share state. The fact that you can use multiple processes to scale is not an interesting statement when comparing python to other languages because it is true for every language out there. I think the GIL has made people in the python community too defensive: the GIL does not prevent from building scalable architectures in many cases, but it still sucks, and it would be better without. That's a limitation (and a tradeoff because it made development and integration with C easier). And there are scalable architectures based on threads (example: http://www.mailinator.com/tymaPaulMultithreaded.pdf http://www.mailinator.com/tymaPaulMultithreaded.pdf) - "thread suck" has became a meme which slightly bothers me in general. Not a panacea, but a good solution when applicable.
    - rtaycher 16y ago
      I thought the key was not managing mutable state. Sharing lots of immutable data can probably shave a lot of performance over ipc.
ilcavero 16y ago
~$5k for 7 KLOC of bug free C code is a steal, that's impossible to do in less than a couple of months
- kragen 16y ago
  It's nearly impossible to do in any timeframe. I can think of perhaps two examples in human history where I think it's been done: qmail and seL4. And there may still be bugs in qmail. There may be a few other non-public projects that have achieved less than one bug per 7000 lines of C, but probably not more than one or two.
  - fanf2 16y ago
    http://www.dt.e-technik.uni-dortmund.de/~ma/qmail-bugs http://www.dt.e-technik.uni-dortmund.de/~ma/qmail-bugs There are also some DNS-related bugs that are not on this list.
    - kragen 16y ago
      Thanks! I hadn't seen those, although I knew of 1.4. I think 1.1, 1.3, and 1.4 are actual bugs, if the reports are accurate; I'm pretty sure Dan disagreed with Wietse about 1.1. Three bugs in about 15000 lines of code doesn't quite rise to the level of less than one bug per 7000 lines of code, so maybe that's only been done once, in seL4. What are the DNS-related bugs?
- abcd_f 16y ago
  Beg to differ on both points. Ignoring the 7 KLOC metric (which is fairly useless in estimating the project value for the customer), $5K at $100/h rate of a senior C programmer on a contract works out to about 6 working days, which is a reasonable timeframe for writing well optimized XML-RPC protocol parser. In other words it's neither a steal nor does it take two months to write. (edit) YMMV by a programmer, but that's what it would've taken me to write it (though I have written a good deal of protocol parsers).
  - 16y ago
HockeyBiasDotCo 16y ago
Agreed.
DanielRibeiro 16y ago
I Guess Linus also made another suggestion which he didn't pursue on this paragraph: Generational garabage collectors tend to never re-use hot objects, and often do the copying between generations making things even worse on the cache The suggestion? Just reuse hot objects. Note, this post is from 2002. Garbage collectors have improved a lot over the last 9 years. Don't evaluate new technology with such old arguments.
- jeffdavis 16y ago
  Linus was quite specific about his problems with GCs. Just saying that "garbage collectors have improved" without specifics, and calling his arguments "old" doesn't add much information. Can you tell us how they have improved in ways that address Linus's specific concerns? And explain how a generational garbage collector can effectively re-use freshly freed objects before they leave the cache? Which 2011 generational GCs take advantage of that idea?
  - ekidd 16y ago
    Reusing hot memory is a pretty ancient GC technique, though the details have varied over the decades. You can Google "nursery generation" for some examples: http://www.google.com/search?q=gc+nursery+generation http://www.google.com/search?q=gc+nursery+generation The original theory was that most objects in a functional language are extremely short-lived, and you want to reclaim them quickly. But if you GC your nursery generation after every few kB of allocations, you'll also keep the memory in L1 and L2 cache. The ideal size of a nursery generation (and the value of reusing hot memory) should be measured empirically. Of course, most popular scripting language GCs are non-copying, reference-counting collectors, which means they ignore techniques that were well-understood back in the 80s. However, this has not been a barrier to the adoption of Python, Ruby, etc., because the business value of high-performance code is often minimal.
  - ori_b 16y ago
    You can bypass the GC entirely, and keep the objects that really should be in cache live, and just reuse them. Not a pretty solution, but it's doable.
yid 16y ago
Please don't take this personally, but the fact that your code was N thousand lines doesn't mean the task is inherently an N-thousand line task. Also, undertaking anything with XML in C is brave, kudos.
- ekidd 16y ago
  If you know of any way to make the code shorter and more concise, please let me know. I'm always looking for ways to improve. https://gist.github.com/937200 https://gist.github.com/937200 (two sample files, totaling slightly less than half the project) Posting 10-year-old code to HN is always a little embarrassing, but please feel free to be brutal. I'll live. :-) I was definitely way too in love with the preprocessor back then. Here's the corresponding Python code, from shortly after it hit 1,000 lines in late 2001: http://hg.python.org/cpython-fullhistory/file/7b2d701ec404/Lib/xmlrpclib.py http://hg.python.org/cpython-fullhistory/file/7b2d701ec404/L... I like the Python code rather better, if only because there's so much less explicit memory management. The actual ideas stand out clearly, and there's just so much less code to read. In most cases, I'd happily sacrifice the performance.
ondrasej 16y ago
Actually, geting reference counting right and mostly bug-free is much easier, if you use C++ and do the counting via objects on stack (RAII).
- VeXocide 16y ago
  Absolutely not, http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1450.html http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1450.ht... explains why in section D. Implementation difficulty
  - pjkundert 16y ago
    Actually, yes. The boost::smart_ptr<...> is highly effective. Prior to that existing, I wrote a similar ref-counting library that has been deployed to hundreds of remote sites, running high-reliability industrial control code. While complex, the ref-counting implementation gave me something that a GC system just can't deliver: Determinism. This system is running on a 300MHz embedded x86 hosts, in a solid-state industrial computer, and has to provide sub-millisecond timing with only occasional hiccups >1ms acceptable. I am unaware of a GC system that could deliver this. These boxes run for years, with no memory leaks. The cost was, of course, ensuring that no "loops" of objects get created. This was a small price to pay for the benefits. Having written large systems using both GC and ref-counting, I still lean toward ref-counting, even if determinism isn't a strong requirement. Of course, I'm one of those guys who loves C++, so take my opinions with a grain of salt...
    - marshray 16y ago
      I, too, love C++ and the boost smart pointer library. In fact, it's been adopted into modern versions of the C++ standard itself. std::tr1::shared_ptr and std::shared_ptr.
    - skorgu 16y ago
      IBM's Metronome[1] advertises maximum pause times in the hundreds of microseconds range. Cliff Click[2] cites a 10MB max heap for it so definitely not a cure-all but definitely something I'd like to play around with. [1]http://domino.watson.ibm.com/comm/research_projects.nsf/pages/metronome.metronomegc.html http://domino.watson.ibm.com/comm/research_projects.nsf/page... [2]http://www.youtube.com/watch?v=uL2D3qzHtqY http://www.youtube.com/watch?v=uL2D3qzHtqY
joe_the_user 16y ago
Was my library about 50 times faster? Sure, I could parse 1,500+ XML-RPC requests/second. Did anybody actually benfit from this speed? Probably not. Then your (client's) problem wasn't reference counting but premature optimization. Are there situations where you'd like to have code run fifty times faster than native Python. You bet there are, lots and lots of them - for example, in a Unix-clone Kernel. Sorry if somehow you didn't find one of them. Hopefully you used Valgrind and Formal language specification to reduce the work required. And to avoid premature optimization, use gprof to find the bottleneck(s) rather than just diving into what seems to need optimization.
- HenryR 16y ago
  You're mixing up 'premature optimisation' and 'unnecessary optimisation'. The first is making code faster that isn't the bottleneck, or dominating performance factor. The second is making something faster than it needs to be. Profiling helps avoid the first, benchmarking helps avoid the second. Both require working (toy) systems, which is hard when you are evaluating which language to begin work in. Writing a library in C (for reasons of performance) where performance would have been 'good enough' in Python is unnecessary optimisation. Writing your own GC implementation layer in Python because you think that's the bottleneck would be premature optimisation. EDIT: typo
  - joe_the_user 16y ago
    Seems like a rather small distinction. Unnecessary optimization is a natural result of premature optimization so I tended to assume that was what was happening. Unnecessary optimization can result from other things as well of course. Regardless of this distinction, I think the same conclusions follow; the original problem had little to do with reference counting as such.
hristov 16y ago
You are probably right, but your experience does not disprove the central point that GC always slows things down. Now this slow down may be worth it in most situations, in fact it may be worth it in 99% of situations, but it is a fact. In some cases that 50 times increase in speed may be important. In some cases, if something is 50 times slower it would be simply unusable. Linus happens to be working on one of those special cases, so he is quite correct in pointing out that garbage collection will always slow things down.
InclinedPlane 16y ago
Context is always important. And there's no such thing as blanket advice that applies to every circumstance. Software development is a hugely varied endeavor, ranging over more orders of magnitude and more variety of application than almost any other industry. It stands to reason that most practices will vary rather considerably depending on context. Linus writes from a systems perspective. He cares about every nanosecond and every byte. And that's appropriate and even laudable in the context of the linux kernel and core applications. But it's not always appropriate for every situation.
known 16y ago
I've used your brilliant XML-RPC in one of my consulting assignments. Thanks.

by ekidd 16y ago

ekiru 16y ago

Linus suggested in the OP that automated reference counting (where the language implementation handles reference counting for the programmer) is preferable to GC. Python uses such reference counting (although it also has a GC fallback to ensure cyclic structures are collected).

cdavid 16y ago
And it is one of the reason why python is slow and difficult to scale on multiple cores (the main difficulty by far of removing the GIL is reference counting).
- kragen 16y ago
  Scaling Python on multiple cores is easy: you just run multiple Python processes, each with its own per-core GIL. You are correct, though, that ref-counting overhead is one of the main reasons Python is slow.
  - cdavid 16y ago
    You are playing with words here: of course you can run multiple python instances to scale your application on multiple-cores, that's a trivial statement. But I was talking about python the interpreter (more exactly cpython). There are legitimate cases where multi-threading is the natural, elegant solution, and cpython, mostly because of reference counting, prevents that.
    - kragen 16y ago
      CPython prevents you from using shared-state multithreading to scale your application on multiple cores, but it doesn't prevent you from scaling your application on multiple cores. That's not "playing with words". It is indeed unfortunate when the limitations of our platforms force us to contort our code to improve performance, but that is just as true of multithreading as of multi-process programming. The difference between the complexity of the two is small.
  - gerner 16y ago
    Thank you for making this point. To my great dismay I see more and more people think that you need concurrent threads in one process in order to scale. It seems as if many programmers believe this as scripture and subsequently have difficulty thinking about distributed systems (not just multi-core, but multi-host).
  - SpikeGronim 16y ago
    The drawback with multiple processes is that they each have all the compiled bytecode on their heap. When I "import nltk" my heap goes from ~12 to ~36 MB. Add a few more dependencies and you end up wasting a non-trivial amount of RAM on python heaps.
    - lobster_johnson 16y ago
      You could do the import and then fork the child processes. That should share all the memory used by the nitk module between all the children (for as long as the memory is not modified by anyone, which triggers a copy-on-write allocation of the affected pages).
- jrockway 16y ago
  C and Java apps with high contention don't scale well onto multiple cores, either. The key to speed is to not share state, which Python can do fine. It's called fork.
  - cdavid 16y ago
    Sometimes you cannot easily not share state. The fact that you can use multiple processes to scale is not an interesting statement when comparing python to other languages because it is true for every language out there. I think the GIL has made people in the python community too defensive: the GIL does not prevent from building scalable architectures in many cases, but it still sucks, and it would be better without. That's a limitation (and a tradeoff because it made development and integration with C easier). And there are scalable architectures based on threads (example: http://www.mailinator.com/tymaPaulMultithreaded.pdf http://www.mailinator.com/tymaPaulMultithreaded.pdf) - "thread suck" has became a meme which slightly bothers me in general. Not a panacea, but a good solution when applicable.
  - rtaycher 16y ago
    I thought the key was not managing mutable state. Sharing lots of immutable data can probably shave a lot of performance over ipc.

ilcavero 16y ago

~$5k for 7 KLOC of bug free C code is a steal, that's impossible to do in less than a couple of months

kragen 16y ago
It's nearly impossible to do in any timeframe. I can think of perhaps two examples in human history where I think it's been done: qmail and seL4. And there may still be bugs in qmail. There may be a few other non-public projects that have achieved less than one bug per 7000 lines of C, but probably not more than one or two.
- fanf2 16y ago
  http://www.dt.e-technik.uni-dortmund.de/~ma/qmail-bugs http://www.dt.e-technik.uni-dortmund.de/~ma/qmail-bugs There are also some DNS-related bugs that are not on this list.
  - kragen 16y ago
    Thanks! I hadn't seen those, although I knew of 1.4. I think 1.1, 1.3, and 1.4 are actual bugs, if the reports are accurate; I'm pretty sure Dan disagreed with Wietse about 1.1. Three bugs in about 15000 lines of code doesn't quite rise to the level of less than one bug per 7000 lines of code, so maybe that's only been done once, in seL4. What are the DNS-related bugs?
abcd_f 16y ago
Beg to differ on both points. Ignoring the 7 KLOC metric (which is fairly useless in estimating the project value for the customer), $5K at $100/h rate of a senior C programmer on a contract works out to about 6 working days, which is a reasonable timeframe for writing well optimized XML-RPC protocol parser. In other words it's neither a steal nor does it take two months to write. (edit) YMMV by a programmer, but that's what it would've taken me to write it (though I have written a good deal of protocol parsers).
- 16y ago

HockeyBiasDotCo 16y ago

Agreed.

DanielRibeiro 16y ago

I Guess Linus also made another suggestion which he didn't pursue on this paragraph: Generational garabage collectors tend to never re-use hot objects, and often do the copying between generations making things even worse on the cache The suggestion? Just reuse hot objects. Note, this post is from 2002. Garbage collectors have improved a lot over the last 9 years. Don't evaluate new technology with such old arguments.

jeffdavis 16y ago
Linus was quite specific about his problems with GCs. Just saying that "garbage collectors have improved" without specifics, and calling his arguments "old" doesn't add much information. Can you tell us how they have improved in ways that address Linus's specific concerns? And explain how a generational garbage collector can effectively re-use freshly freed objects before they leave the cache? Which 2011 generational GCs take advantage of that idea?
- ekidd 16y ago
  Reusing hot memory is a pretty ancient GC technique, though the details have varied over the decades. You can Google "nursery generation" for some examples: http://www.google.com/search?q=gc+nursery+generation http://www.google.com/search?q=gc+nursery+generation The original theory was that most objects in a functional language are extremely short-lived, and you want to reclaim them quickly. But if you GC your nursery generation after every few kB of allocations, you'll also keep the memory in L1 and L2 cache. The ideal size of a nursery generation (and the value of reusing hot memory) should be measured empirically. Of course, most popular scripting language GCs are non-copying, reference-counting collectors, which means they ignore techniques that were well-understood back in the 80s. However, this has not been a barrier to the adoption of Python, Ruby, etc., because the business value of high-performance code is often minimal.
- ori_b 16y ago
  You can bypass the GC entirely, and keep the objects that really should be in cache live, and just reuse them. Not a pretty solution, but it's doable.

yid 16y ago

Please don't take this personally, but the fact that your code was N thousand lines doesn't mean the task is inherently an N-thousand line task. Also, undertaking anything with XML in C is brave, kudos.

ekidd 16y ago
If you know of any way to make the code shorter and more concise, please let me know. I'm always looking for ways to improve. https://gist.github.com/937200 https://gist.github.com/937200 (two sample files, totaling slightly less than half the project) Posting 10-year-old code to HN is always a little embarrassing, but please feel free to be brutal. I'll live. :-) I was definitely way too in love with the preprocessor back then. Here's the corresponding Python code, from shortly after it hit 1,000 lines in late 2001: http://hg.python.org/cpython-fullhistory/file/7b2d701ec404/Lib/xmlrpclib.py http://hg.python.org/cpython-fullhistory/file/7b2d701ec404/L... I like the Python code rather better, if only because there's so much less explicit memory management. The actual ideas stand out clearly, and there's just so much less code to read. In most cases, I'd happily sacrifice the performance.

ondrasej 16y ago

Actually, geting reference counting right and mostly bug-free is much easier, if you use C++ and do the counting via objects on stack (RAII).

VeXocide 16y ago
Absolutely not, http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1450.html http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1450.ht... explains why in section D. Implementation difficulty
- pjkundert 16y ago
  Actually, yes. The boost::smart_ptr<...> is highly effective. Prior to that existing, I wrote a similar ref-counting library that has been deployed to hundreds of remote sites, running high-reliability industrial control code. While complex, the ref-counting implementation gave me something that a GC system just can't deliver: Determinism. This system is running on a 300MHz embedded x86 hosts, in a solid-state industrial computer, and has to provide sub-millisecond timing with only occasional hiccups >1ms acceptable. I am unaware of a GC system that could deliver this. These boxes run for years, with no memory leaks. The cost was, of course, ensuring that no "loops" of objects get created. This was a small price to pay for the benefits. Having written large systems using both GC and ref-counting, I still lean toward ref-counting, even if determinism isn't a strong requirement. Of course, I'm one of those guys who loves C++, so take my opinions with a grain of salt...
  - marshray 16y ago
    I, too, love C++ and the boost smart pointer library. In fact, it's been adopted into modern versions of the C++ standard itself. std::tr1::shared_ptr and std::shared_ptr.
  - skorgu 16y ago
    IBM's Metronome[1] advertises maximum pause times in the hundreds of microseconds range. Cliff Click[2] cites a 10MB max heap for it so definitely not a cure-all but definitely something I'd like to play around with. [1]http://domino.watson.ibm.com/comm/research_projects.nsf/pages/metronome.metronomegc.html http://domino.watson.ibm.com/comm/research_projects.nsf/page... [2]http://www.youtube.com/watch?v=uL2D3qzHtqY http://www.youtube.com/watch?v=uL2D3qzHtqY

joe_the_user 16y ago

Was my library about 50 times faster? Sure, I could parse 1,500+ XML-RPC requests/second. Did anybody actually benfit from this speed? Probably not. Then your (client's) problem wasn't reference counting but premature optimization. Are there situations where you'd like to have code run fifty times faster than native Python. You bet there are, lots and lots of them - for example, in a Unix-clone Kernel. Sorry if somehow you didn't find one of them. Hopefully you used Valgrind and Formal language specification to reduce the work required. And to avoid premature optimization, use gprof to find the bottleneck(s) rather than just diving into what seems to need optimization.

HenryR 16y ago
You're mixing up 'premature optimisation' and 'unnecessary optimisation'. The first is making code faster that isn't the bottleneck, or dominating performance factor. The second is making something faster than it needs to be. Profiling helps avoid the first, benchmarking helps avoid the second. Both require working (toy) systems, which is hard when you are evaluating which language to begin work in. Writing a library in C (for reasons of performance) where performance would have been 'good enough' in Python is unnecessary optimisation. Writing your own GC implementation layer in Python because you think that's the bottleneck would be premature optimisation. EDIT: typo
- joe_the_user 16y ago
  Seems like a rather small distinction. Unnecessary optimization is a natural result of premature optimization so I tended to assume that was what was happening. Unnecessary optimization can result from other things as well of course. Regardless of this distinction, I think the same conclusions follow; the original problem had little to do with reference counting as such.

hristov 16y ago

You are probably right, but your experience does not disprove the central point that GC always slows things down. Now this slow down may be worth it in most situations, in fact it may be worth it in 99% of situations, but it is a fact. In some cases that 50 times increase in speed may be important. In some cases, if something is 50 times slower it would be simply unusable. Linus happens to be working on one of those special cases, so he is quite correct in pointing out that garbage collection will always slow things down.

InclinedPlane 16y ago

Context is always important. And there's no such thing as blanket advice that applies to every circumstance. Software development is a hugely varied endeavor, ranging over more orders of magnitude and more variety of application than almost any other industry. It stands to reason that most practices will vary rather considerably depending on context. Linus writes from a systems perspective. He cares about every nanosecond and every byte. And that's appropriate and even laudable in the context of the linux kernel and core applications. But it's not always appropriate for every situation.

known 16y ago

I've used your brilliant XML-RPC in one of my consulting assignments. Thanks.