Thanks to Elyn, my t-shirt design from last year’s GCC Summit is now available.
I made a new GCC t-shirt yesterday, but you’ll have to wait for the summit to see it.
Archive for the ‘software’ Category
Parsing
I was reading about PEG recently, and thinking “that is pretty interesting” — and of course it turns out that there is an Emacs implementation.
It is a bit odd how primitive parsing support is in Emacs. It is one of those mysteries, like how window configuration and manipulation support can be so weak. Peculiar.
CEDET includes a parser generator, called wisent. That is long overdue… though even it is a bit odd, apparently preferring a yacc-ish input syntax. I don’t know about you, but when I have a lisp system just sitting there, I reflexively reach for sexp-based formats. Well, ok, it is a port of bison. But still.
I did a little parser hacking in gdb recently. In gdb, if you complete an expression involving a field lookup, it will currently print every matching symbol in your program — when all you really wanted was the completion of a field name. This is what I set out to fix.
My first idea was: hey, the parser knows what tokens are valid. I can just ask it! But, I don’t think there’s a way to do that with bison parsers. At least, no documented way — boo. And anyway, as it turns out, this is not what you want.
For instance, consider the simple case of “p pointer->field“. This is syntactically valid as-is, so the parser would indicate that the desired completions are whatever can come next — say, an operator. But if the cursor is just after the “d”, you want to continue completing on the field name. So, you have to differentiate this case based on whitespace.
I ended up hacking the lexer as well as the parser. The lexer can now return a special COMPLETE token, which it does depending on the previous tokens and the presence or absence of whitespace. I also added some new productions like:
expression: expression '.' name COMPLETE expression: expression '.' COMPLETE
From here it is pretty simple to solve the rest of the problem.
I don’t remember reading about this anywhere, but I’m sure it has been done before. I thought it was a pretty fun hack 🙂 – I love problems that start with the user experience and end up someplace much deeper.
Would you do it again for free?
Thursday night I finally made it to a BLUG meeting. Stormy Peters from OpenLogic gave a talk titled “Would you do it again for free?”
Her talk covered some familiar ground — intrinsic versus extrinsic motivation, a list of motivations that free software developers claim (or that are claimed by others), the various methods of payment. Her slides were beautiful; she seemed a bit nervous though not overly so.
She also talked a bit about inequality in projects. She claimed that 40% of developers on free software projects are paid to do so; a show-of-hands at the meeting showed similar results.
OpenLogic is running the Open Source Census — kind of a cross-platform popcon. If you read her blog a bit you’ll see that she uses this information when talking to VCs and the like. That’s a smart idea and I’m generally in favor of hard data over speculation anyhow.
She was using an Asus, kinda cool. And Neil, sitting next to me, was using an XO. Weird times we live in.
Motivation, of course, is a psychological phenomenon, one with which we all have direct experience. That is, everybody has an opinion… so one commenter from the audience rejected most of her list of motivations in favor of — you guessed it — his. I suppose this is the bikeshed effect in a different form.
I didn’t agree with everything in Stormy’s talk. At one point she gave a sort of economic history of mankind which, I think, was badly mistaken on the facts, though perhaps not our experience of them.
After the talk I asked her about the pretty photos and consistent palette in her presentation. She said they were CC-licensed works from flickr and from some stock photo site… nice. (Also I noticed her slowly backing away while we talked. Whoa! Like, I’ve always been afraid of being that person. And now … hard data. Crap.)
She also talked a bit about the relationship developers have with open source. One idea was that a hacker might leave a project (suppose the project dies) — but will just switch projects and keep working. Also, supposedly nowadays open source developers make more money than proprietary developers; but, conversely, often claim that they would take a pay cut to work on open source (the intrinsic motivation thing). Let’s hope our bosses stop midway through that sentence.
I’m fascinated by the social dimension of programming. Partly this is defensive; over the years I’ve developed some heuristics that I use to evaluate developers (sorry. But it is true. And of course I like you.) and projects, mostly to try to keep away from painful experiences. But, I’m also interested in a more general taxonomy of projects — my suspicion is that many of the things we think we know about running projects either aren’t so, or are “don’t care” boxes in the Karnaugh map of administration. What is cool is that the free software movement is so big, now, that we have an excellent laboratory in which to study.
Codegen Update
Since my last post, I’ve written a prototype implementation of relinking for the incremental compiler.
Now, the compile server will create an object file in a cache directory. If there was a previous variant of the compiled file in the cache, it will then link the two together (using ld -r). Then, the final object file is copied from the cache to the user’s requested output file.
So, now you can “make clean; make” and see correct results from the incremental compiler. The new results table:
| Compiler | Seconds |
|---|---|
| Trunk | 30 |
| Incremental, no server | 30 |
| Server, first run | 26 |
| Server, second run | 17 |
This is probably the current best (or “best worst”) case — no actual recompilation needed to be done. In terms of user scenarios, this corresponds to, say, modifying a comment in a core header file and recompiling. And, given that this is execing both ld and cp, the results aren’t too bad.
On the other hand, I had somewhat higher expectations. I’ve been pretty depressed about this project all week. Relinking is turning out to be a pain; I’m pretty much convinced now that incremental preprocessing is a necessity; and this combination makes me wonder whether I’m chasing a rat down a hole. The question of whether this project remains worthwhile is normative one, and fairly subjective. That’s a fancy way of saying, I don’t know.
Ugh.
Mostly I try to think about it in terms of a success metric. Or, what is the minimum expected gain that would make it appear to be worthwhile? I suspect I may need to prototype the C++ compiler changes before I can really satisfy myself on that topic, though.
Back to the concrete.
The linking prototype is still pretty bogus. It arrives at an executable which works, but the intermediate object files grow over time. That’s because it is pretty hard to coerce ld (and objcopy) into doing the odd things I want: I want to link two files together, yielding another relinkable object (i.e., I need -r), where symbol name clashes are always resolved in favor of the first file. You’d think -z muldefs (I’ve gotten overly familiar with the ld manual) would work here, but it just drops the symbols — not the contents. So, maybe -ffunction-sections and --gc-sections is the way to go — but this also has problems; the former because (supposedly) it does not work with all programs, and the latter because it interacts oddly with -r.
I’m still hoping I can get by with a relatively simple linker hack, though as the week has dragged on I’ve realized that my understanding of linking is less than ideal.
First Codegen Result
I tidied up my initial draft of incremental code generation so that it no longer gratuitously lowers functions which are not being recompiled. This was enough to get some results — results which are semi-bogus, due to not relinking, but which nevertheless give some idea of what can be expected.
| Compiler | Seconds |
|---|---|
| Trunk | 33 |
| Incremental, no server | 33 |
| Server, first run | 27 |
| Server, second run | 14 |
| Preprocess | 4 |
So, the results are a bit odd. Recompiling is fast, as we’d expect — about twice as fast as a plain build. However, it still falls far short of the time used by the preprocessor. What is going on in there?
A look with oprofile seems to indicate that the excess is spread around. About 10% of the total time is spent in the GC; another 7% is used computing MD5s. Other than that… if I add up the top 40 or so non-cpp functions, I get about 5 seconds worth, and there is a long tail after that. That’s a bummer since that kind of problem is hard to fix.
Setbacks
The last couple weeks uncovered a few problems in the incremental compiler.
First, suppose you compile a program with the incremental compiler, then recompile it. You would expect to get the same warnings as well. But — whoops — I never thought about this until a week or two ago.
I hate that awful moment of realization. It reminds me of getting in trouble as a kid. “Oh shit”, I think. “What am I going to do? Does this sink the project?”
In this case, there are some options. If the set of warning flags does not change between compilations, I think I can modify GCC to store the warnings with their corresponding declarations. This is a bit of a pain, but nothing too awful — and I think I can avoid imposing a cost on the non-warning case by representing the warnings as tree objects and storing them in the hunk with the other declarations.
If the user does change the warning flags, then what? Record it and recompile, I guess. A similar idea applies to options that change the ABI — because ABI decisions get baked into the tree objects we create, if the ABI changes, we cannot reuse the trees.
My other uh-oh moment has to do with inlining. I got bored by the tedious sub-projects I was working on — integrating pragmas (by the way. If you design a language, don’t design pragmas. Thanks) into the dependency computation, fixing the remaining test suite failures — so I decided today to start looking at incremental code generation. Something fun!
I tried out a quick implementation. If a function is parsed, we arrange to compile it; if it is not parsed, we don’t bother. This won’t work on real programs, of course, since those “missing” functions have to come from somewhere, but this should give a good idea of the possible speedup.
After testing on my typical small test program (zenity), I noticed something odd, namely that recompilations were not as blazingly fast as I thought they should be. (I first estimated the absolute lower bound as the time it takes to preprocess the source files.)
Hmm. A mystery. But first, a brief aside about tools. The compile server forks and runs code generation in the subprocess. I wanted to debug this fork. So, Plan A: use gdb and set follow-fork to child. But… that fails because, although my program does not use threads, it still links in the thread library (relic of my failed threading experiment), and gdb does not seem to handle this well. So, Plan B: maybe ftrace from frysk can help me — all I want to do is see a stack trace at a particular function call, perfect for ftrace. But, the ftrace I have aborts at startup. So I update and rebuild — but there is a build error. I suppose I could have gone with Plan C: stick in a sleep() call and attach, just like I did 15 years ago. Instead I picked Plan D: printf. Not quite as good, since I still need some of that information. Somehow I didn’t feel like Plan E: rip out the threading code and start over at Plan A.
Right now I’m doing a lot of debugging and pretty much every week has a vignette like that. I didn’t do that python stuff in gdb purely for fun.
Anyway. What is going on in the compile server?
What I found is that the code generation process still does some processing on every function, even functions that we intend to drop. In particular it is lowering each function to GIMPLE. I think what is going on here is that GCC is lowering functions and running local optimizations on them so that they can be considered as candidates for inlining. At least, that’s my working theory until I get back to Plan C and dig around a bit.
I’m not totally sure yet what to do about this. I think I will have to go back and rip out the decl re-smashing pass I wrote a while back, and instead find a way to perform gimplification in the server. That way, the compile server can keep the gimplified form for use by the back end. Other than the work involved, and some tricky details in lowering without smashing, I think this will work.
This isn’t going to be pretty, but at least it isn’t a total disaster. I’d like to think this isn’t totally an accident. GCC has undergone a lot of changes in the last five years to make it more flexible internally, and I’ve pushed a little bit more in that direction on the branch. This makes it a bit simpler to change the point at which we put a fork in the pipeline.
It feels a bit strange to write about the mistakes I make. On the plus side, I know how to fix these problems; writing about really unknown problems would, of course, be beyond the pale.
Random Updates
I heard about Dolt recently. This is a minimal replacement for libtool that works only on Linux. It seems like a great idea, long overdue… though of course for new programs you should just use Quagmire, which, as I’ve said before, replaces libtool with two lines of code.
I’m into lisp these days, so much so that I’ve considered ranting about it here. I’ve read CLtL2 and I plan to read another online CL book. Anyway, I ran across this funny-ish lisp comic yesterday.
Elyn’s latest blog entry made me laugh out loud.
Steve Yegge’s new javascript mode for Emacs is now in ELPA — if you use js you should check it out.
Emacs News
An awesome color theme for Emacs.
Steve Yegge wrote a new javascript mode for Emacs. I’m interested in modes that push Emacs a little and do real parsing rather than the typical (and goofy) parse-partial-sexp stuff; this one falls into that category. Semantic also does this, though more generically and perhaps with more sophistication; I think semantic parsers are born incremental. I hope to push this mode into ELPA as soon as he responds to my patch…
Using Python in Gdb
Today I used the Python support in gdb to do real work. Until now I’ve just been playing around, adding functionality that looked fun.
My application was something I’ve wanted to be able to do in gdb for a long, long time: set a breakpoint in one function, but have the breakpoint be conditional on the caller. In my case, I’m debugging the compile server, and I want to examine calls to c_parser_lookup_callback which pass a complicated test (that is, the breakpoint is in the true branch of an if statement); but only calls originating in declspecs_add_type are interesting.
Roland taught me that you can fake this in plain gdb by using convenience variables and breakpoint commands. However, it is rather painful to get this right, as you have to remember to reset the convenience variable in some cases (in my case, if we reach the outer breakpoint but not the inner one).
With the Python support, this kind of thing is easy. First I define a Python function to do a little work:
(gdb) python Type python script End with a line saying just "end". >def check(): > frame = gdb.current_frame().get_prev() > return frame.get_name() == "declspecs_add_type" >end
As you can see this just checks the parent frame’s function name.
Now, I make the breakpoint conditional on this function’s value:
(gdb) cond 1 $(check())
That’s all there is to it!
I suppose I could have written this as a one-liner, like:
(gdb) cond 1 $(gdb.current_frame().get_prev().get_name() == "declspecs_add_type")
Both of the above formulations still seem a little clunky to me. But, it is still early days for the Python integration; I think we’ll find some nice ways to simplify common tasks.
What’s your missing feature?
Emacs and Threading
While once again waiting for Gnus to contact a news server, I thought: I’ll never be able to move my RSS reading into Gnus, because the delays will skyrocket. Sure, there’s nntp//rss, but that means configuring a separate program and keeping it running — and I’ve heard that this program can have a memory footprint as big as Emacs itself. (As an aside: remember the old days when Emacs was routinely the program with the largest footprint on your desktop? For me it is never number one, and sometimes even slips to 3 or 4.)
Maybe some savior will come along and make Gnus fetch RSS feeds in the background, using a process filter. I assume, without looking, that retro-fitting this into Gnus would be very hard. For new Emacs code, though, this is the way to go; you can set things up so that most mode-specific operations report “working…” back to the user when background operations are happening — while still letting the user switch buffers and work on other things. For instance, nowadays vc-annotate works this way, which is very nice, since annotate is fairly slow in most version control systems.
Even better would be to make Emacs capable of multi-threading. Most people arrive at this idea eventually. Unfortunately, I think it is just not possible; partly due to bad language choices: dynamic scope is very handy, but having only dynamic scope is terrible; but also partly due to consequent design choices for the rest of Emacs: buffers are big global objects, maintaining compatibility for the enormous body of existing lisp is crucial, and auditing even the built-in body of elisp is, in difficulty, somewhere between daunting and impossible.
A few weeks ago I heard a funny idea in this area. Instead of trying to handle multi-threading, how about old fashioned multi-process support, with some kind of message passing? Emacs could fork(), and then the child could wander off with its own copy of everything; and then the subprocess could send up messages and data which would be integrated into the Emacs event loop. This is basically the same idea as process filters, only with the benefit that the process could be expressed in the same lisp form as the handler, and the subprocess would have access to all the relevant lisp state.
Naturally, most of these messages would just be elisp; but perhaps it would be worthwhile to add a way to transfer the contents of a buffer wholesale.