Not much of a post
Not much of a post
some thoughts on transactional memory
Intel has been around the office lately to talk to us about transactional memory and the panacea that it's going to be. Like any silver bullet, it's only effective against werewolves - and fortunately (or unfortunately) there aren't any werewolves attacking me at the office.
Transactional Memory (or TM) is a process by which multiple processes/threads update shared memory within a 'transaction' similar to a commit by a RDBMS. A transaction will only commit if all updates to memory complete successfully without conflicts. In the case of a conflict we roll back execution to where we started.
To give TM a little bit of credit though, it does solve a certain set of problems in concurrent programming. Basically TM allows the programmer to minimize the amount of time they worry about getting locks, freeing locks, and probably more importantly debugging why there's a deadlock in the program when something happens with a lock. We call this the SPOD problem at work - "Spinning Pizza of Death". This will make sense to those of you who own a Mac.
Of course, right now TM is mostly an exercise left to the student (from "The Landscape of Parallel Computing Research: A View From Berkeley"):
Transactional memory is a promising but still active research area. Current software-only schemes have high execution time overheads, while hardware-only schemes either lack facilities required for general language support or require very complex hardware. Some form of hybrid hardware-software scheme is likely to emerge, though more practical experience with the use of transactional memory is required before even the functional requirements for such a scheme are well understood.
Nothing comes without a cost though, some estimates of STM implementations have them incurring a 40-50 percent overhead compared with locking based programming. STM also incurs an additional performance hit if it has to guarantee interoperation between TM code and other code.
The future, I think, holds a couple of directions that will need to go in umm... parallel. We'll need things like transactional memory to deal with things at a low level. We'll also need to do better than source level markup of existing languages to fully take advantage of many core programming. For example, TM is well suited for applications that want to use mutexes or shared memory. We'll need a better way of representing producer/consumer models where message passing is better suited. All in all an interesting time.
Had a chance to work with a coworker (Howard Hinnant) lately on a language standardization issue, in this case std::thread:
It was quite an interesting experience. I found that mostly reading and learning how other people are approaching the various issues was the way this time. I'm glad to have been able to listen in as everyone discussed how the proposal should work. I did make a few contributions that seem to have been appreciated so I look forward to things in the future.
All in all I think Howard's proposal shaped up quite nicely and will be useful as we start to approach concurrency issues in more current use languages in the future.
Blog that I found somewhere through a link to a link to a link or something:
Rands In Repose
turns out he's a coworker (one of the 15,000 or so), and never met him in person.
Still, lots of interesting reads there.
Lots of gcc work going on...
No, not much by me lately outside of darwin maintenance for Apple, but some interesting stuff anyhow:
Mem-SSA: Diego's work here is finally merged with mainline
Dataflow branch: Kenny Zadeck's work along with a cast of others (Daniel Berlin, Seongbae Park, Codesourcery)
gimple-tuples, out-of-ssa: memory savings, speed ups clean ups done by Aldy and Andrew
IPA: Jan is merging the IPA branch stuff
autovectorization: as always... the group in haifa is doing great work here
loop optimizations: zdenek's work here rewriting things
and more coming... I'll see if I can write information up on each of these.
verdict in the tripoli 6 trial
Today a Libyan court condemned five Bulgarian nurses and a Palestinian doctor to death even after the scientific evidence has pointed to their innocence. There is the possiblity that it's a great extortion plot as Bulgaria was asked to provide reparations - but even so once again the barbarians have won a battle on science.
good UI and useful too
I'm not really one to pimp something just because it has a pretty interface, but David
getting around dull software maintenance
Software maintenance is dull. No one wants to do it, people would much rather be writing new code - or at least that's how the line usually goes. Most programmers think that software maintenance is either a drudge task or fixing bugs in code that others write. it can really be a time for an engineer to go back and rethink code that's written. After you've fixed the 3rd or 10th or 200th bug in a section of code you often end up with something that resembles spaghetti (from combine):
/* Don't eliminate a store in the stack pointer. */
if (dest == stack_pointer_rtx
/* Don't combine with an insn that sets a register to itself if it has
a REG_EQUAL note. This may be part of a REG_NO_CONFLICT sequence. */
|| (rtx_equal_p (src, dest) && find_reg_note (insn, REG_EQUAL, NULL_RTX))
/* Can't merge an ASM_OPERANDS. */
|| GET_CODE (src) == ASM_OPERANDS
/* Can't merge a function call. */
|| GET_CODE (src) == CALL
/* Don't eliminate a function call argument. */
|| (CALL_P (i3)
&& (find_reg_fusage (i3, USE, dest)
|| (REG_P (dest)
&& REGNO (dest) && global_regs[REGNO (dest)])))
/* Don't substitute into an incremented register. */
|| FIND_REG_INC_NOTE (i3, dest)
|| (succ && FIND_REG_INC_NOTE (succ, dest))
/* Don't substitute into a non-local goto, this confuses CFG. */
|| (JUMP_P (i3) && find_reg_note (i3, REG_NON_LOCAL_GOTO, NULL_RTX))
/* Don't combine the end of a libcall into anything. */
/* ??? This gives worse code, and appears to be unnecessary, since no
pass after flow uses REG_LIBCALL/REG_RETVAL notes. Local-alloc does
use REG_RETVAL notes for noconflict blocks, but other code here
makes sure that those insns don't disappear. */
|| find_reg_note (insn, REG_RETVAL, NULL_RTX)
/* Make sure that DEST is not used after SUCC but before I3. */
|| (succ && ! all_adjacent
&& reg_used_between_p (dest, succ, i3))
/* Make sure that the value that is to be substituted for the register
does not use any registers whose values alter in between. However,
If the insns are adjacent, a use can't cross a set even though we
think it might (this can happen for a sequence of insns each setting
the same destination; last_set of that register might point to
a NOTE). If INSN has a REG_EQUIV note, the register is always
equivalent to the memory so the substitution is valid even if there
are intervening stores. Also, don't move a volatile asm or
UNSPEC_VOLATILE across any other insns. */
|| (! all_adjacent
&& (((!MEM_P (src)
|| ! find_reg_note (insn, REG_EQUIV, src))
&& use_crosses_set_p (src, INSN_CUID (insn)))
|| (GET_CODE (src) == ASM_OPERANDS && MEM_VOLATILE_P (src))
|| GET_CODE (src) == UNSPEC_VOLATILE))
/* If there is a REG_NO_CONFLICT note for DEST in I3 or SUCC, we get
better register allocation by not doing the combine. */
|| find_reg_note (i3, REG_NO_CONFLICT, dest)
|| (succ && find_reg_note (succ, REG_NO_CONFLICT, dest))
/* Don't combine across a CALL_INSN, because that would possibly
change whether the life span of some REGs crosses calls or not,
and it is a pain to update that information.
Exception: if source is a constant, moving it later can't hurt.
Accept that special case, because it helps -fforce-addr a lot. */
|| (INSN_CUID (insn) return 0;
This is what Joel is talking about here when he says:
"When you throw away code and start from scratch, you are throwing away all that knowledge. All those collected bug fixes. Years of programming work."
Now, this code is ugly. It should probably be rethought and refactored a bit, but not rewritten completely. There's another area in that file that's a single function that is more than a thousand lines long. Should that be rethought? Probably. Deleted and rewritten from scratch? Unlikely.
This is how you turn dull software maintenance tasks into exciting new times: you periodically go back and rethink code, it's part of maintenance too and it gets you doing "new" code while doing the necessary bug fixing that got you into that code in the first place. A good rule of thumb is that every time you fix a bug you should try to clean up the surrounding code in some way so that the next person that goes through has an easier time than you did - and you don't lose the benefit of all of the years of bug fixing in that area.
type sizes in C vs bit sizes
An interesting difference between C type sizes and the architectures that they're hosted on has come across in a rather annoying manner since I've been working on byteswapping builtins for gcc. The standard library function (for integers at least) comes in the standard, long, and long long styles, e.g. ctz, ctzl, ctzll. This has some odd side effects for things which usually return a value of the size of a register or the size of the input. Writing a general routine when you're using a cross compiler is difficult because it depends on the size of the type on the target machine which isn't always readily available. This is why a lot of these routines should be based on the size of the type that was wanted - based on the types in stdint.h for example.
For the new byte swapping builtins I followed this idea, we now have __builtin_bswap32 and __builtin_bswap64 which take and return types of int32_t and int64_t respectively. We needed to add some additional size specific types into gcc for this, but it'll help when we want to specify additional builtins of this sort. Hopefully future revisions of the various standards will have standard libraries that require sizes and types instead of just types.
mythical man month
This post on silver bullets is a great one. Makes you realize that while some software is just poorly designed, software engineering is an incremental process and that anyone that thinks different is fooling themselves. The author is mostly talking of fad technologies, but I also remember another paper of the problem with "throw-it away and design it again" software engineering. Sometimes you can do it better again. Most of the time you can't and just end up wasting a lot of time and money. The Mythical Man-Month should be required reading for all software engineering managers - and not as a "we can do better than that" document.
New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.
Keep up with the latest Advogato features by reading the Advogato status blog.
If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!