sb

Seconded! Especially with magit (and I suppose with vc in general) key chords are really nice.

I started using emacs about seven years ago after about eight years of exclusively using vim, primarily because I wanted to see what the editor war's were all about (and because I got the blues from work and needed something uplifting...) I agree with the learning curve, and constantly am fine tuning my setup and configuration, but once you've mastered the basics, it truly becomes one of the most powerful editors. Plus it is constantly evolving (e.g., multiple cursors).

Another good emacs guide that I came across recently is:

http://m00natic.github.io/emacs/emacs-wiki.html

Additional resources I found helpful:

http://www.emacswiki.org/emacs/EmacsNiftyTricks

http://web.psung.name/emacstips/essential.html

Plus, check out the videos from Magnar Sveen's emacs rocks:

http://emacsrocks.com

In general many commenters have a misconception that the mentioned French "baccalaureate" is related to the US/UK undergraduate bachelor's degree. As the article points out, and the corresponding wikipedia page hints at, this somewhat roughly translates to a high school diploma in the US, the British A-levels, the German Abitur, etc.

There is an interesting comment that illustrates the distinction between US/Europe education systems by observing that in Europe high schools are general followed by focused specific subject studies, whereas in the US there is a lot of focusing already happening in the high schools. Interestingly, though, there seems to be a general education requirement for an undergraduate degree; since I am from Europe this seems to have the purpose of ensuring that all admitted students get to the same level before specializing.

Managing free memory is indeed an interesting problem. Besides the simple free-list approach sketched by the author (sidestepping the first-fit vs. best-fit search strategy, which affects fragmentation, too), I always found the buddy-list to be particularly interesting:

https://en.wikipedia.org/wiki/Buddy_memory_allocation

Unfortunately, the article is not a very good explanation, I remember having seen a drawing of the data structure, but cannot recall from where...

edit:

It turns out that the mentioned jemalloc internally uses buddy lists as well.

A couple of years ago, I read his paper "Definitional Interpreters for Higher Order Languages" [1], because it was suggested to me by a friend. It was a joyful read, and to the best of my knowledge it is the first treatment of how to implement higher-order language constructs in a first-order language. Just recently, I thought of the paper, so it's sad news that the author has died...

[1] http://repository.readscheme.org/ftp/papers/plsemantics/reyn...

ABC, always be coding.

I tried Oberon once and have to say that it was way ahead of its time. Not only did the author (of the linked paper) invent one of the first JIT compiled systems, but also the ability to execute code with a mouse click (similar to Rob Pike's ACME editor) is---for a systems programming language---still not available today.

There were several novel research ideas tried for the Oberon system. I remember there was some paper called "Active Text" that allowed putting videos into code comments. (Probably that could have been done in Smalltalk, too.)

Finally, all of the books explaining details are heartily recommended. Wirth's compiler book (referred to at HN several times) is a classic easy-going introduction (the Oberon-0 grammar fits on only two pages IIRC! [1]), his algorithm book (also available for download, also referred to multiple times at HN) has some of the nicest descriptions that I did not find anywhere else (showing a divide-and-conquer approach to computing the median [near the Quicksort treatment]; plus polyphase sort, which might be useful again in data centers), and finally the Project Oberon book contains some unique treatment on system software that is not easily found anywhere else. For example, it contains the details on what's called PieceLinkText, which is the (at least AFAIK) best data structure to implement a text editor and it's operations. (Predating rope-strings by a fair amount of time, too.)

edit:

[1]: just checked my own copy; Oberon-0's grammar actually fits on one page, the full Oberon grammar fits on two pages!

[2]: URLs:

- Compiler book: http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

- Algorithm book: http://www.inf.ethz.ch/personal/wirth/books/AlgorithmE1/AD20...

- Project Oberon: http://www.inf.ethz.ch/personal/wirth/books/ProjectOberon.pd...

ad 1: Please also do keep in mind that there are career steps after obtaining tenure. If you say "Fuck it" right after getting tenure, you are almost certain to never make it thus far.

I also do agree with the other comment regarding funding agencies. Another problematic way that NSF does business (inviting professors for peer review that is) is that this virtually guarantees that some of your peers know exactly what you're doing, which reduces effectiveness of double-blind submissions substantially (to the point where it is hard to believe it works at all; didn't it ever occur strange to anyone that the same people from the same top schools are consistently successful? [with grants and publications in the top venues])

I know these from the site, and have looked at the Django benchmark that's listed there. I think it's a rather small benchmark that does exercise lots of Django internals (but that benchmark comes from Unladden Swallow). I don't know for the twisted ones, though.

What I actually wanted to know, what the biggest application is, i.e., a not benchmark.

ad 1) Hm, this seems to be a good point, but what's with the following line of thinking: some thread A interprets a program P, while another thread B compiles P to native machine code (P'). Now, if another thread C would start executing P' (taking the data/snapshot from A), then C's caches should build up and remain accurate. Of course, if this happens too often, then the caching behavior will be shitty. I always wondered (based on my interest in interpretation), how much I-cache misses the instruction cache flushes after inline-caching in native machine code cause. (If you have some data on that, please let me know.)

ad 3) I am well aware of that. However, I remember that at PLDI'11 there was a talk from Univ. of Edinburgh chaps doing parallel trace-based dynamic binary translation. Obviously, DBT is less work than a high level, full-blown JIT, but at least it's not nil :)

Interesting point of view, the problem in compiler construction is well known ("Proebsting's law", though it says it's more like 18 years instead of 10.)

The issue with benchmarks is surely well known, also by the PyPy authors; I wonder what the biggest application is that they have benchmarked or that runs on PyPy.

Your point on the JIT compiler interrupting program execution is certainly valid, too, but not necessarily so. One could easily do the code generation in a separate background thread and let execution switch over only if necessary. But, as you have already said, a latency issue certainly exists. This is one of the cases where interpreters usually have a leg up, and there are promising ways of optimizing interpreters.

Hm, there are already some comments about possible optimizations kicking in and asking for assembly code (which is always a good idea to look for changes). However, before doing all of these things, I would want to know how these results were measured? How many repetitions, which machine configuration, standard deviation, etc. It could very well be that this behavior is due to some pre-caching in Windows or some other external factor.

I agree that it is all about cost, however this is far more "local" to many US citizens than they might imagine. For example, most of the coke bottles outside of the US come in half litres, while in the US they come in 20 fluid ounces (this is certainly true for many other products, too.) Hence, companies that make coke filling machines must accommodate the imperial system on top of the metric system, as well. Given that the metric system company can easily grab most of the market share, it should eventually be able to get larger economies of scale. In the end, it could very well be that machinery to supply imperial unit sized products becomes more expensive, a cost that will most certainly be relegated to the consumer.

This year I either read, or started to read the following interesting books:

Mathematics: Form and Function by Saunders Mac Lane. This is one of my favorite books concerning the "build-up" of mathematics (it also contains nice diagrams of "relatedness" of subjects). On HN somebody once recommended Mathematics: Its contents, methods, and meaning (from Russian mathematicians in the 50s) which is similar but without the cross references.

Proofs and Refutations by Imre Lakatos. I have started reading this only recently and have to say that I find the approach and idea excellent. It would be great if we had something comparable for CS theory as well.

Notes on Introductory Combinatorics by Polya, Tarjan, and Woods. Have not read this exhaustively, but the introduction with Pascal's triangle and some of Polya' legendary problem solving insights (paraphrased from my memory: "you are on to something once you find a pattern") are definitely highlights in this book.

Mathematical Discovery: On Understanding, Learning and Teaching Problem Solving by George Polya. Based on the previous book and my fond memories of reading "How to Solve it", I got this one from the library. Again I can't attest for all of the contents, but AFAICT now it's another gem from Polya.

From HN advice in previous years I read The Tibetan Book on Living and Dying, which I can heartily recommend, too. It is an anti-thesis to Christian theology and I find it to contain many insightful comments and different views on leading a good, meaningful life. I disagree with some of the church-y comments on that it really is important to have a master and that only the master can do certain things, but that's probably just me being an atheist all along.

I actually read some other books, but the list is already kind of long and might hold interesting pointers for other mathematically inclined readers, too. I for one am always fascinated on how much advice on problem solving in mathematics translates to CS.

Nice article (the Stanford Encyclopedia of Philosophy has many more, btw.), but I like the "Introduction to Lambda Calculus" by Henk Barendregt (one of the people working in Lambda calculus, see for instance the citation to his book "The Lambda Calculus: Its syntax and semantics." in the references), which has the added benefit of being free:

http://www.cse.chalmers.se/research/group/logic/TypesSS05/Ex... (also covers typed lambda calculus AFAIR)

I love that one, and it always surprises me when I meet people who can't express themselves properly. There are some of the earlier EWDs, where he meets a lot with German computer scientists (in particular one of the founding fathers of the field there, Friedrich L. Bauer, whom he calls "Uncle Fritz"), and it seems that he had good understanding of German, too.

There is also an interesting video of Dijkstra from a Netherland's television station (http://www.cs.utexas.edu/~EWD/video-audio/NoorderlichtVideo....)

In college I was reading a lot of the EWDs (particularly his trip reports, some hilarious stuff there) and IIRC he didn't like C/C++ a lot and thought that functional programming has some promising ideas. This was in the later EWDs, I'd say 1150+.

There are some fun quotations of him about APL and Basic.

I usually recommend E.T. Jaynes' "Probability Theory: The Logic of Science", which is one of the most beautiful and comprehensive books on the subject.

To get the "logic of science" part, you also need to have (IMHO) some fairly decent grasp of combinatorics, for which I quite recently stumbled upon one of the best books in this field: "Notes on Introductory to Combinatorics." (I like the links to many of Polya's gems of "How to solve it.")

For many other references, a quick HN search for publicly available references will result in other endorsements, too (a preliminary version of the Jaynes' book used to be available, too)

Hm, I have never really thought about NLP, but I guess maintaining an NLP program somebody else has written must be even more of a nightmare than what we have now...

You're not really "giving up" portability, only with ANSI C. For all architectures where GCC is available, its labels-as-values support will happily compile and hence give you a fully portable instruction dispatch.

Regarding the threaded code: the literature seems to be horribly inconsistent in this regard. Token threaded code might actually refer to indirect-threaded code depending on what the author has read. I was actually quite surprised to read what "indirect threaded code" originally meant when I read Debaere and van Campenhout's 1990 book "Interpretation and Instruction Path co-processing".

Regarding the effect of CSE & tail-merging: I have only seen GCC to do this once, by disabling basic block reordering (-fno-reorder-blocks, due to a so-called "software trace cache"), otherwise this has never happened to me. Since I have nothing but the highest respect for Mike Pall, I guess that he might have experienced this for Lua, which has--to the best of my knowledge--less than 40 instructions. I will try to verify this on the weekend.

Ok, well even for dynamic languages threaded code is likely to give you a noticeable speedup. The only negative example I'm aware of was adding threaded code (+superinstructions) to the Tcl interpreter, which resulted in slowdowns sometimes.

Even though the potential is not going to be as big as for Java, Forth, and OCaml interpreters (where people frequently report 2x speedups), for example Python gains between 20 and 45%. But somebody already replied to a similar inquiry and said that ANSI C compatibility is more important than the increase in performance. (Python uses conditional compilation to achieve both.)

This is somewhat different from my memory. AFAIR, TraceMonkey was a trace-based JIT. JaegerMonkey was a JIT (however not just-in-time like V8 with a template-based JIT, but still using an interpreter initially). IonMonkey is--to the best of my knowledge--JaegerMonkey plus type inference (there was a paper by two Mozilla employees at PLDI'12 about their type inference.) So I guess it's not really using anything from trace compilation.

I think a trace-JIT still gives you a lot of bang for the buck and is (in theory at least) easier to implement. Two known projects using trace-compilation are LuaJIT2 (usually well known) and Dalvik VM's JIT compiler (not so well known, needed to watch the Google I/O 2010 announcement.)

AFAICT, two reasons come to mind:

1) A stack-based ISA is still more space-compact. (AFAIR the Shi et al. paper mentions something like a 40+% increase in space requirement for the instructions.)

2) The performance improvement of a register-based ISA is only visible for interpreters that suffer most from instruction dispatch [1]. PHP is a rather complex programming language that is most certainly not bound by instruction dispatch at all. So I guess it could very well make sense to stick with a simple stack-based ISA, which incidentally is also easier to compile from the AST.

[1] for the sake of completeness: the stack architecture emits many instructions to push operands onto the operand stack. A register-based interpreter does not need those. Hence, the overall number of dispatches is lower, and if dispatch cost is your bottleneck the overall performance increases. OTOH, you need more space, because in addition to the opcodes, you need to specify/encode which registers to take operands from and put results to. (Hint: quadruple code and the likes.)

I don't know about the exact definition of "mainstream bytecode-based VM", but just for the record: both the OCaml interpreter and the GForth interpreter usually score pretty well, too.

Probably the de facto fastest interpreter is the one of the Sun HotSpot Java virtual machines. There is a paper by Robert Griesemer detailing some information, but AFAIR it is a hand-coded optimized assembly interpreter that does not too bad. LuaJIT's interpreter is doing quite well, too. (Mike Pall said in the LTU thread about trace-based compilation that the LuaJIT2 interpreter is mostly on par with the LuaJIT1 compiler, or at least not much slower.)

EDIT: replaced "LuaJIT1 interpreter" with more accurate compiler as pointed out by haberman.

Some hints for your quest:

- Linux's perf tool allows you to read HW performance counters. It's pretty self-explanatory, and some interesting ones are platform-neutral, whereas others you have to specify the CPU manufacturer's hex-code. (See Intel manual, for example.)

- For pipelining and HW/CPU details, I suggest you grab a copy of Hennesy and Patterson's Computer Architecture: A Quantitative Approach. There is also Computer Architecture: A Programmer's Perspective, which is good, but I think for what you're interested in, CAAQA is the better book.

- If you just want to play around with HW performance counters, you might want to try Intel's vtune, which comes (or at least did so, two years ago) as an Eclipse plugin/RCP-workbench.

Hm, thanks for the nice remark on the game stuff, I kind of like that.

While agree with your primary criticism, I think the principle of locality applies well to this problem. While there are 24 million places (supposedly, never checked that from the paper), I'm positive that most maps queries are served to the areas with higher population density. Therefore, it might make sense to use the look-up table approach for densly populated areas to reduce the search time. (OTOH, the computer scientist in me reminds me that the 7ms might pale in comparison to latency times for mobile phones receiving the map information...)

Thanks so much for all the data! I was just about to write a "well, hopefully nobody on HN cares about these rankings" post, trying to remember some of the facts I read about, but your post summarizes these data so well, no need to post at all.

Just for the record: I recently read (presumably on HN, too) about a ranking where somebody asked lawyers to rank schools according to their prestige. Penn-State always got ranked in the middle, even though it didn't have a law school at all. So, in a sense it doesn't even matter if administrators are cheating or not...

It's a brilliant book, a professor at my university used it for teaching SECD machine implementation. I'm glad that I could get it from the library. If you're interested in these kind of things, Henderson's "Functional Programming -- Application and Implementation" might also your thing. (IIRC the list did not contain it.)

The original lambda papers might be on your want-to-read list, too: http://library.readscheme.org/page1.html; I liked the AIM-453 TR, "The Art of the Interpreter, or, The Modularity Complex" by G. Steele and G. Sussman.

There is also another project named HappyJIT doing much of what is described there. The corresponding paper was presented at last year's Dynamic Languages Symposium [http://dl.acm.org/citation.cfm?id=2047854]

It would be nice if there were comparable benchmark results available, or a discussion of what is different between both approaches/implementations.

EDIT: bb link didn't work, replaced it with ACM portal link.