131–140 of 207 posts
We should really encourage eachother to put the date in the title when submitting old articles to HN. It's a total brainf*k to read through the entire article, and not realize the context it was in.. or to just glance at the title and assume the topic is a current one. Just saying. [Edit] Not that I have a problem with older posts, btw.. I actually really like them most of the time. But the date would give everyone a…
Date: Fri, 9 Aug 2002 20:28:16 -0700Here are a couple of reasons why I think it's not so clear cut: 1. If garbage collection was that damaging to the cache, Haskell wouldn't be nearly as fast as C. 2. Copy-on-write data structures are nice because the immutability allows for concurrent access without locking. Granted, this was from 2002 and Linus may no longer feel so strongly about the topic.
Show me a memory-intensive kernel in which Haskell runs close to the performance model. Sparse and dense matrix kernels would be a good place to start. Our C code for sparse matrix-vector products and sparse triangular solves gets better than 90% of STREAM bandwidth (based on an assumption of optimal cache reuse, STREAM is about 85% of hardware peak). Dense matrix kernels should get better than 90% of FPU peak. Unlik…
Or teach the compiler about the algebra of arrays and matrices, so it can do the things to the code, that we'd write by hand.
E.g.
* http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp...
* http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.p...
* http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf
* http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf
In all these cases arrays codes are written in a function style, accompanied with special purpose optimizations and/or code generators (in the case of GPU code), layered over an imperative arrays primitive layer, using a memory effects monad.
Couldn't agree more. We were actually laughing in the office when an office mate brought up such a paper many years ago.
"I really think it's the mindset that is the biggest problem."
Linus is a superhero 20+ years working on the supertask of changing people's mindset.
Earlier quoted context omitted.
is the ref counting slow because it has to be a protected operation? or is it just the amount of them. if it is due to being protected by locks there are lock free ref counting systems (as described in here: http://www.google.com/url?sa=t&source=web&cd=1&v... ) that essentially allow batch refcounting opterations to accumulate in a per thread counter that are only reconciled occasionally. assuming you design your dat…
That's awesome! I knew there were faster approaches to ref-counting, but I didn't know about that one, "sloppy counters". The most common approach to speeding up ref-counting is to ref-count bigger objects — modules rather than individual variables, say. The simplest way to speed up ref-counting transparently is to statically analyze the code and remove redundant increment and decrement operations. This can be tricky…
We should really encourage eachother to put the date in the title when submitting old articles to HN. It's a total brainf*k to read through the entire article, and not realize the context it was in.. or to just glance at the title and assume the topic is a current one. Just saying. [Edit] Not that I have a problem with older posts, btw.. I actually really like them most of the time. But the date would give everyone a…
Date: Fri, 9 Aug 2002 20:28:16 -0700
Earlier quoted context omitted.
Absolutely not, http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1450.ht... explains why in section D. Implementation difficulty
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…
[1]http://domino.watson.ibm.com/comm/research_projects.nsf/page... [2]http://www.youtube.com/watch?v=uL2D3qzHtqY
Earlier quoted context omitted.
Show me a memory-intensive kernel in which Haskell runs close to the performance model. Sparse and dense matrix kernels would be a good place to start. Our C code for sparse matrix-vector products and sparse triangular solves gets better than 90% of STREAM bandwidth (based on an assumption of optimal cache reuse, STREAM is about 85% of hardware peak). Dense matrix kernels should get better than 90% of FPU peak. Unlik…
> It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad. Or teach the compiler about the algebra of arrays and matrices, so it can do the things to the code, that we'd write by hand. E.g. * http://www.cse.unsw.edu.au/~benl/paper…
The single threaded Handwritten C version is about 45% faster than our best Haskell result, which is achieved with 3 threads.
Meanwhile, there is no performance model so we don't know how good the C version is. The paper doesn't even report a simple fraction of FPU or bandwidth peak. It is not using SSE instructions so it cannot possibly be better than 50% of FPU peak (the limit is actually lower because this kernel is/should be bandwidth limited). As for parallelism, I'll quote Bill Gropp [1]
The easiest way to make software scalable is to make it sequentially inefficient.
[1] http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&#...
Earlier quoted context omitted.
Implementing a stop-the-world, 2-space copying GC, provided you have complete stack, register and type layout data, is trivial. Implementing reference counting is much less so, especially in the presence of threads. Many simple scenarios turn into problems of lock-free programming proportions - and that's just for verifying that memory safety is present, not that the user hasn't introduced bugs with their own threadi…
I've implemented both in C++. See http://svn.boost.org/svn/boost/trunk/boost/smart_ptr/shared_... as an example of reference counting. Add in some atomic increment/decrement primitives and that's literally all there is to implement in one header file. But even the lightest weight GC collector I could make had a significant C++ implementation file with lots of nontrivial pointer operations and loops in it. Even withou…
Earlier quoted context omitted.
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.
That's a valid point, but you can do things to mitigate this, like splitting up your program into processes that have different dependencies. For instance, if you have a UI process and a core logic process, you won't need to import your giant UI library twice.
Earlier quoted context omitted.
I agree with Torvalds on this matter. In a way, I do as well. GC as it is promoted today is a giant step that gives programmers one benefit, solving one problem, while introducing a immeasurable pile of complexity to the system creating another pile of problems that are still not fixed today. And to fix some of these problems (like speed) you have to introduce more complexity. There are plenty of contexts where speed…
> I've seen generational GC perform admirably, almost magically. As a lark, I've put infinite loops into such apps that do nothing but allocate new objects While I agree that generational GC can perform spectacularly well, what you're describing is close to the case it's optimized for, not close to its worst case. The worst case is that you allocate lots and lots of small objects and then write a pointer to all of th…
Here's the thing: Most of the rest of the app was rather close to the case it's optimized for.
I don't know what you mean by "something like LINT but for the runtime reference graph."
Something that tells you that you've created a reference graph with a cycle, you have a memory leak, or that you're using references in some other stupid or suboptimal way. I'm not even sure if there's a way to automatically detect anything like the last category, though the first two are certainly detectable. Basically, you take most of the infrastructure of GC, and you just turn it into a runtime advisor to warn devs and testers of mistakes.