Not much of a post

But I thought I'd mention that Ian is writing a series of posts on writing a new linker. The first post is here.

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.

std experiences

Had a chance to work with a coworker (Howard Hinnant) lately on a language standardization issue, in this case std::thread:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2184.html

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.

worth reading

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

Watanabe's new project Inquisitor has both style and use.  It wraps up a pretty interface

in a very useful piece of software. It has perhaps the best interface I've seen to search

in a long time.  There's also a very pretty Safari plugin for it that wraps up the interface,

and like most of those sorts of things allows a bit of customization too.  I've been using

it for about a week now and it has quickly become one of my favorite extensions for

any piece of software.

A quick plug on one of David's other projects: NewsFire. A good OS X application that

I've been using for a while now and it's quite nice.

Links:

http://www.inquisitorx.com -- Inquisitor

http://www.inquisitorx.com/beta -- Inquisitor Web Interface

http://newsfirerss.com -- NewsFire

Edit: re-edited to help the layout. Blogger Beta is painful

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) < FIRST_PSEUDO_REGISTER
&& 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))
#if 0
/* 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)
#endif
/* 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) < last_call_cuid && ! CONSTANT_P (src)))
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.

current projects

I've been working on various bits of compiler work for Apple lately. A lot of the public work that's been seen has been of the cleanup variety - fixing up testcase failures from previous releases. However, I've also been working on some bugs relating to the object file format. We've made some recent maneuvers toward having a more sane definition in the toolchain - moving toward linker generated gots and plts, but for a great deal of the existing toolchains this would require a lot of work.

In my previous work I hadn't needed to work around limitations in the object file format - at least not in any great degree. Sure the MIPS ABI could use some changes, and there definitely aren't enough bits in the elf flags field for all of the various instruction sets or processors for the target. In the grand scheme of things these are small peanuts. Mach-O (or macho) is the format that was chosen at work about the time that work on OS X was begun.

Mach-O isn't very flexible. The object file format contains bitfields, not the least of which is for relocations. There are 4 bits of relocations available to a single architecture. For those of you counting at home this gives you 16 relocations. The fact that mach-o by default defines five of them leaves an architecture 11 additional relocations that you can define. Under ELF even the x86 port has 38 relocations, including the ones for TLS. The PowerPC mach-o port is out of relocations completely and yet if we had another 4 bits we probably couldn't do all of the TLS relocations we should have. If we want to get rid of the the compiler generated stubs, or have compiler generated thread-local storage a new way of defining relocations is needed. Or we could move to ELF.

Assorted Hacking

Lately I've been dealing with the random bugs of close to release software. The 64-bit eabi stuff is giving UNPREDICTABLE results for a simple:

la reg,0x80000000

macro instruction. Now, I hate macro instructions. There's never an excuse for not saying exactly what you mean if you're going to bother to write assembly in the first place. Especially in cases like this - there are over 2 thousand lines of code in gas just to deal with the la and li macros - and have I mentioned that we don't document them anywhere?

I mean anywhere. One of the canonical bibles of the MIPS architecture is the Kane and Heinrich book. It describes this instruction as "an addiu and an lui if needed". This description is so woefully inadequate that it's hard to specify what the input to the macro should be. If it's an absolute expression like we have above it doesn't specify if we should sign extend the address before adding it. The method of least surprise says that we should. Then there's whether or not we should warn about this questionable behavior. Right now, we do - but only for n64.

The other question is whether or not you should just use the fully qualified address for both 32 and 64-bit cases. This would solve the problem, and is indeed allowed by gas, but it's a little iffy in my book.

I suppose I should start adding all of these things to the wiki page here: MIPS Assembly Programming Wikibook.

Just remember kids, assembler macros are a tool of the devil.

First Entry

Trying out the new blog interface over here. Rather disappointed with Livejournal so I decided to move over here. Much nicer for the first few blogs. Hopefully a change of pace on the entries as well.