Tenerife Skunkworks

Links for 2009-11-06 [del.icio.us]

Sat, 07 Nov 2009 00:00:00 PST

Links for 2009-11-03 [del.icio.us]

Wed, 04 Nov 2009 00:00:00 PST

Using Mathematica to create a daily list of Trade Weight Index data « Wildebeests

Tracking IO patterns in memory-mapped dynamic libaries

Mon, 02 Nov 2009 15:21:07 +0000

The Mac OSX dynamic linker uses mmap to load dynamic libraries into memory. The memory range occupied by the libraries is then backed by a set of virtual memory pages, chunks of 4096 bytes each.

Using mmap is efficient because pages are lazily loaded from disk as needed and the virtual memory pager is free to evict them behind the scenes when memory is needed for something else.

Each page is filled with code for functions that live in the dynamic library and pages are fetched from disk when a call is made to a function in the dynamic library.

Pages should be accessed sequentially for best performance but how do you find out if this is the case? The only way to find out is to plug into the virtual memory manager and track when pages backing a particular dynamic library are paged-in from disk.

This is doable but a tad complicated as it requires access to internal kernel structures. As always, DTrace comes to the rescue! Note that the following DTrace script will only work on Snow Leopard. Let’s take it apart and see how it works…

First we define a an alias for an internal kernel type. This is not necessary but saves on typing.

typedef struct nameidata* nameidata_t;

A dynamic library is usually opened with a call to dlopen. The first argument (arg0) is the library path.

pid$target::dlopen:entry
/arg0/
{
  self->ppath = arg0;
  self->dylib = 1;
}

The Mac OSX dynamic linker (dyld) does not use dlopen on dynamic libraries, though, so we need to do different.

pid$target::dyld??loadPhase5*:entry,
pid$target::dyld??loadPhase4*:entry
/!self->dylib && arg0/
{
  self->path = copyinstr(arg0);
  self->func = probefunc;
  self->dylib = 1;
}

We want to trigger subsequent probes only if we entered via one of the two entry points above. We need to reset the flag once we return and this is what we do below.

pid$target::dlopen:return
{
  self->dylib = 0;
}

pid$target::dyld??loadPhase5*:return,
pid$target::dyld??loadPhase4*:return
/self->func != 0 && self->func == probefunc/
{
  self->dylib = 0;
}

It often happens that memory we want to access in DTrace is not available at the function entry point. This is what happens sometimes with the dlopen entry probe. The open call is triggered by dlopen so we can copy the file path into kernel space using the self->ppath pointer we saved earlier.

/* file name memory should be wired in by now */

pid$target::open:entry
/self->dylib && self->ppath && self->path == 0/
{
  self->path = copyinstr(self->ppath);
}

The Mac OSX virtual memory manager identifies a file by its virtual node (vnode) in the virtual filesystem (VFS) layer. We need to somehow match up the dynamic library name with its vnode and this is where the vn_open_auth entry probe comes in.

Note that unlike the DTrace pid$target provider we used before, we use the Function Boundary Tracing (FBT) provider since the virtual filesystem layer lives in the kernel.

fbt::vn_open_auth:entry
{
  self->ndp = (nameidata_t)arg0;
}

This clause is not absolutely necessary but I’m populating self->curpath as a shortcut, to be used a few times in later probes.

/* wait to make sure ndp and vnode are fully populated */

fbt::vn_open_auth:return
/self->path != 0/
{
  self->curpath = stringof((self->ndp)->ni_pathbuf);
}

It’s not obvious how to best match up a vnode with a file name so I cheated and studied the XNU kernel source code which Apple makes available. The vnode is not populated until vn_open_auth returns so we have to wait until it happens fo fetch the path.

We are almost done with our task, just need to save the library name and library path to vnode mappings if our library names match.

/* make sure we are opening the same file */

fbt::vn_open_auth:return
/self->curpath != 0 && self->path == self->curpath/
{
  this->vp = (vnode_t)(self->ndp)->ni_vp;
  this->lib = stringof((this->vp)->v_name);
  self->lib[this->lib] = self->path;
  self->vnode[this->lib] = this->vp; 
}

We do need to clean up sometime and so we do.

fbt::vn_open_auth:return
{
  self->path = 0;
  self->ppath = 0;
  self->curpath = 0;
  self->ndp = 0;
  self->func = 0;
  self->dylib = 0;
}

We use the same function boundary tracing (fbt) DTrace provider to track page-ins. We print the file offset of the data we are paging in, as well as the size.

fbt::vnode_pagein:entry
{
  self->v_name = stringof(((vnode_t)arg0)->v_name);
}

/* vnode pointers should match but v_name seems more secure */

fbt::vnode_pagein:entry
/self->lib[self->v_name] != 0/
{
  printf("vnode_pagein: %s, offset: %u, size: %u\n", 
    self->v_name, arg3, arg4);
}

It does look from the output that we are loading multiple pages at the same time, e.g. size 1019904 corresponds to 249 pages. Page access looks quite random, though, which is killing us.

Now that we know what the access pattern is, we should try to first identify the symbols that are being accessed in each set of pages and then make the linker rearrange the code such that page access is more sequential and less random.

Note that you are not likely to see page-ins when running this DTrace script unless you have just restarted your Mac and are running Firefox for the first time. This is because the dynamic libraries will be stored in the Unified Buffer Cache (UBC) after first access and there won’t be any subsequent disk access until they are evicted from the cache.

I wrote about hacking the Unified Buffer Cache before but the same technique does not work with mmap-ed data since the virtual manager and the cache are the same thing. Evicting the libraries would involve allocating at at least twice as much virtual memory as there’s RAM and then touching each page to make sure it’s cached. This is unlikely to correspond to normal use of Firefox, though.

Links for 2009-10-31 [del.icio.us]

Sun, 01 Nov 2009 00:00:00 PDT

Apple Approved iPhone Inter-process Communication

Links for 2009-10-24 [del.icio.us]

Sun, 25 Oct 2009 00:00:00 PDT

A Log of an Attempt to Port SBCL to Linux on the ARM Architecture

Links for 2009-10-20 [del.icio.us]

Wed, 21 Oct 2009 00:00:00 PDT

Links for 2009-10-15 [del.icio.us]

Fri, 16 Oct 2009 00:00:00 PDT

Links for 2009-10-14 [del.icio.us]

Thu, 15 Oct 2009 00:00:00 PDT

My Firefox for Mac startup optimization log

Wed, 14 Oct 2009 13:40:40 +0100

My Firefox for Mac startup optimization log

My notes on Firefox for Android

Wed, 14 Oct 2009 13:38:39 +0100

My notes on Firefox for Android

Automated Trading Resources | Flirting wiht Models

Mon, 05 Oct 2009 15:17:50 +0100

Automated Trading Resources | Flirting wiht Models

Erlang and high-frequency trading

Thu, 01 Oct 2009 21:11:06 +0100

Erlang and high-frequency trading

"I knew a Chinese guy who came to the US with his mom, dad, and sis. They all worked at a Chinese..."

Sun, 13 Sep 2009 12:04:22 +0100

“

I knew a Chinese guy who came to the US with his mom, dad, and sis. They all worked at a Chinese buffet and shared an apartment with another family (that’s like 8 people in a 2 bedroom apartment!).

Anyway, since they could eat for free at the buffet, their rent was cheap, and they didn’t do anything but work, every month each family member could save around $1000 (so $4K total).
And so in a year they had $48K saved up!

They did this for 4 years and then had enough to open their own buffet restaurant. And from the looks of it they’re doing quite well. They have a huge house now and luxury cars and stuff.

”

- http://www.reddit.com/r/programming/comments/9jacy/has_anyone_here_successfully_launched_a_start_up/

Where does time go?

Fri, 28 Aug 2009 18:43:30 +0100

The dyld shared cache lives in /var/db/dyld/. The two files of interest are dyld_shared_cache_i386.map (for x86-32) and shared_region_roots/Applications.paths. Both are regular text files. The former shows the contents of the shared cache for the i386 architecture and the latter is what update_dyld_shared_cache inspects.

There’s no prebinding on newer versions of Mac OSX and the dyld shared cache is automatically updated as needed. Tracing Safari disk activity during startup reveals that basically all its dynamic libraries are pulled from the dyld shared cache.

It’s possible to add Firefox (…/Firefox.app/Contents/MacOS/firefox-bin) to Applications.paths and the change will persist across reboots. Unfortunately, only a handful of libraries that Firefox uses are pulled into the cache by update_dyld_shared_cache. I’m speculating that this may have something to do with @executable_path/XUL and friends (otool -L …/firefox-bin).

Safari uses absolute paths to frameworks in /System/Library/Frameworks so I speculate that relative paths are what is preventing XUL and others from going into the cache.

It’s possible to fix relative library paths in a given library, e.g. fix.sh XUL where fix.sh looks like this

#!/bin/bash 

function dylibs () {
  otool -L $1 |grep executable_path|awk '{print $1}'|cut -d"/" -f2
}

for i in `dylibs $1`
do
        install_name_tool -change @executable_path/$i `pwd`/$i $1
done

install_name_tool -id `pwd`/$1 $1

Firefox has to be recompiled with LDFLAGS=-header-pad_max_install_names_ in MOZCONFIG to make this happen since new library paths are greater than the space allocated in the Mach-O binary. See the man page for install_name_tool for details.

It’s possible to force dynamic libraries into the cache by putting dynamic library paths into shared_region_roots/Applications.paths instead of executables. I wasn’t successful in caching XUL, though, regardless of what I did. XUL is the Firefox dynamic library, it doesn’t even have a dylib extension.

In the end it doesn’t seem to matter since there’s a baffling lack of difference between Firefox and Safari cold stats, despite Safari pulling everything from the cache and Firefox using a large number of non-cached dylibs.

Here’s the cold startup stats for Safari

sync && purge && DYLD_PRINT_STATISTICS=1 /Applications/Safari.app/Contents/MacOS/Safari
total time: 696.9 milliseconds (100.0%)
total images loaded:  116 (114 from dyld shared cache, 114 needed no fixups)
total segments mapped: 5, into 30 pages with 10 pages pre-fetched
total images loading time: 204.9 milliseconds (29.4%)
total rebase fixups:  1,298
total rebase fixups time: 0.1 milliseconds (0.0%)
total binding fixups: 2,476
total binding symbol lookups: 234, average images searched per symbol: 1.6
total binding fixups time: 80.5 milliseconds (11.5%)
total bindings lazily fixed up: 3 of 901
total init time time: 411.3 milliseconds (59.0%)
total images with weak exports:  1

and Firefox

total time: 731.2 milliseconds (100.0%)
total images loaded:  106 (93 from dyld shared cache, 56 needed no fixups)
total segments mapped: 49, into 5903 pages with 684 pages pre-fetched
total images loading time: 235.3 milliseconds (32.1%)
total rebase fixups:  149,011
total rebase fixups time: 3.7 milliseconds (0.5%)
total binding fixups: 24,932
total binding symbol lookups: 797, average images searched per symbol: 2.3
total binding fixups time: 149.9 milliseconds (20.5%)
total bindings lazily fixed up: 45 of 19,109
total init time time: 342.2 milliseconds (46.8%)
total images with weak exports:  3

Notice a large and significant difference? Me neither.

The other thing that I cannot explain at the moment is where the rest of the startup time goes, e.g.

./cold.sh startup.d
Total: 10001.723521ms

So it took less than 1 second to dynamically link Firefox but where did the other 9 seconds of startup go?

cold.sh is rather simple

#!/bin/bash

cmd="./Minefield.app/Contents/MacOS/firefox-bin -no-remote -foreground -P 2"

sync && purge && dtrace -x dynvarsize=64m -x evaltime=exec -c "$cmd" -wZs $1

and the startup.d script doesn’t do much either

#pragma D option quiet

BEGIN
{
 start = timestamp;
}

/* stop tracing here */

mozilla$target:::main-entry
{
 exit(0);
}

END
{
 this->total = timestamp - start;
 printf("Total: %u.%06ums\n", this->total / 1000000, this->total % 1000000);
}

main-entry is my static probe, built into the Firefox source code. It fires once the main Firefox function, XRE_main, is entered.

I don’t have an explanation yet but 9 seconds is a very large difference but it just may be DTrace because of similar cold startup timings for Safari and Firefox.

Faster Mac Firefox

Fri, 21 Aug 2009 17:12:00 +0100

I started at Mozilla this Monday and my focus is on making Firefox run faster which includes startup and page rendering.

I thought I’d start by checking dynamic linking time of Firefox and Safari.

My testbed consists of

3 years old 2.16Ghz CoreDuo MacBook Pro, 2Gb of 667Mhz DDR2 memory, 100Gb 7200 RPM hard drive
recent 2.93Ghz Core2Duo MacBook Pro, 4Gb of 1067Mhz DDR3 memory, 256Gb Apple SSD

Running on the latter machine, I have

total time: 5.8 seconds (100.0%)
total images loaded:  116 (114 from dyld shared cache, 114 needed no fixups)
total segments mapped: 5, into 30 pages with 10 pages pre-fetched
total images loading time: 2.4 seconds (42.5%)
total rebase fixups:  1,298
total rebase fixups time: 0.1 milliseconds (0.0%)
total binding fixups: 2,444
total binding symbol lookups: 236, average images searched per symbol: 1.6
total binding fixups time: 895.5 milliseconds (15.3%)
total bindings lazily fixed up: 3 of 889
total init time time: 2.4 seconds (42.1%)
total images with weak exports:  1

for Safari, and

total time: 5.9 seconds (100.0%)
total images loaded:  105 (92 from dyld shared cache, 56 needed no fixups)
total segments mapped: 49, into 5894 pages with 684 pages pre-fetched
total images loading time: 4.4 seconds (74.4%)
total rebase fixups:  148,829
total rebase fixups time: 5.3 milliseconds (0.0%)
total binding fixups: 24,885
total binding symbol lookups: 794, average images searched per symbol: 2.3
total binding fixups time: 350.1 milliseconds (5.9%)
total bindings lazily fixed up: 45 of 17,764
total init time time: 1.1 seconds (19.5%)
total images with weak exports:  3

for Firefox.

From the above I conclude that the dynamic linker is bloody fast, taking minimal time to fix up thousands of bindings (library function pointers, etc.).

I can also conclude that Safari takes twice as long to run its static initializers (total init time).

Dynamic linking is not the bottleneck then, so I must keep digging!

Here are the results for the faster machine and Safari

total time: 623.0 milliseconds (100.0%)
total images loaded:  116 (114 from dyld shared cache, 114 needed no fixups)
total segments mapped: 5, into 30 pages with 10 pages pre-fetched
total images loading time: 216.7 milliseconds (34.7%)
total rebase fixups:  1,298
total rebase fixups time: 0.1 milliseconds (0.0%)
total binding fixups: 2,476
total binding symbol lookups: 234, average images searched per symbol: 1.6
total binding fixups time: 49.2 milliseconds (7.9%)
total bindings lazily fixed up: 3 of 901
total init time time: 356.9 milliseconds (57.2%)
total images with weak exports:  1

as well as Firefox

total time: 792.2 milliseconds (100.0%)
total images loaded:  105 (92 from dyld shared cache, 56 needed no fixups)
total segments mapped: 49, into 5894 pages with 684 pages pre-fetched
total images loading time: 281.0 milliseconds (35.4%)
total rebase fixups:  148,829
total rebase fixups time: 2.6 milliseconds (0.3%)
total binding fixups: 24,885
total binding symbol lookups: 794, average images searched per symbol: 2.3
total binding fixups time: 66.7 milliseconds (8.4%)
total bindings lazily fixed up: 45 of 17,764
total init time time: 441.8 milliseconds (55.7%)
total images with weak exports:  3

The $1000 Erlang challenge

Wed, 15 Jul 2009 23:14:00 +0100

The $1000 Erlang challenge:

Show me how much I suck, receive a $1000 bounty.

The Ultimate Erlang Challenge is on!

Ex-Goldman Erlang programmer steals super-secret high-frequency trading code

Tue, 07 Jul 2009 09:51:00 +0100

Ex-Goldman Erlang programmer steals super-secret high-frequency trading code:

I interviewed with Serge Aleynikov after he left Goldman Sachs, just a short while ago. Decided to stay put rather than continue interviewing at ex-Citadel Misha Malyshev’s Chicago trading startup.

I wonder, though, how exactly does a programmer go from 400K a year at Goldman (very real) to 3 times as much at a hedge fund? How do you make yourself 3 times as valuable or useful?

I asked for 200k which, in retrospect, seems too little. Still, I value my quality of life in sunny Tenerife far more than long hours for high pay in cold and windy Chicago.

Uploading to Rapidshare from Goldman? Copying to his home computer? Claiming that he planned to cull just the “open source bits”? Deleting BASH history? Waving your Miranda rights orally and in writing? I feel for Serge and his three young girls but I think the whole thing is stupid on many levels.

"When one door closes, another will open, but standing in that hallway can be hell. You just have to..."

Fri, 19 Jun 2009 20:47:00 +0100

“When one door closes, another will open, but standing in that hallway can be hell. You just have to persevere. Quite often that dragon of failure is really chasing you off the wrong road and on to the right one.”

- “Failure” speech, Paul Tudor Jones, 2009

What is the point?

Thu, 18 Jun 2009 14:11:00 +0100

What is the point of pushing %EBX just to call the next instruction and pop it?

For example:

 +4 37444c71 pushl %ebx
 +5 37444c72 subl  $0x30,%esp
 +8 37444c75 calll 0x37444c7a
+13 37444c7a popl  %ebx

Is this some kind of an idiom?

Update:

Mistery solved. The code in question is how GCC calculates the Objective-C selector (method pointer).

This is where I live!

Mon, 15 Jun 2009 21:16:40 +0100

This is where I live!

"Don’t worry about people stealing your ideas. If your ideas are any good, you’ll have to ram them..."

Tue, 07 Apr 2009 12:52:00 +0100

“Don’t worry about people stealing your ideas. If your ideas are any good, you’ll have to ram them down people’s throats.”

- Howard Aiken, IBM

How to land your dream job using LinkedIn

Tue, 10 Mar 2009 01:39:54 +0000

How to land your dream job using LinkedIn

indoctrination

Mon, 09 Mar 2009 20:08:18 +0000

indoctrination

Things look scary but looks can be deceiving! That’s...

Mon, 02 Mar 2009 22:55:00 +0000

Things look scary but looks can be deceiving! That’s Tenerife, the island where I live.

"low-level haskell code is usually 3 times harder to write and 3 times slower than gcc code. native..."

Sat, 28 Feb 2009 15:34:17 +0000

“low-level haskell code is usually 3 times harder to write and 3 times slower than gcc code. native haskell code is tens to thousands times slower than C code”

- ghc vs gcc thread at fa.haskell

OCaml+LLVM vs C++

Mon, 23 Feb 2009 16:49:00 +0000

I’m prone to cooking with too many ingredients and my latest project is a great example. I want to build a Mac trading platform and it must allow EasyLanguage for writing of trading systems. I have a parser already written in OCaml and I would like to compile EasyLanguage rather than interpret. I want vectorization and huge optimization speedups. This is where LLVM comes in.

LLVM has excellent OCaml bindings but code generated by the LLVM just-in-time (JIT) compiler cannot call out to OCaml. I would need to generate C wrappers for OCaml code using LLVM, basically wrapping my OCaml trading platform in C code. The alternative is to write the trading platform in C or C++ but where does that leave OCaml? Is there a huge benefit to OCaml when I’m only using it to implement the parser? I don’t think so!

That leaves me actively looking at using Boost::Spirit for the parser and C++ for the rest of AlgoKit. It’s often said that the right thing to do is the thing you are most afraid of. I have conquered Erlang, OCaml, Haskell and Lisp but I’m scared of C++. Would you believe it?

Cooking with too many ingredients.

Mon, 23 Feb 2009 16:48:04 +0000

Cooking with too many ingredients.