Comparing Schemes of Dynamic Dispatch in C
May 4th, 2009
Schemes of Dynamic Dispatch under Study
The performance of three dynamic dispatch schemes were examined. I also pontificate on the merits of my favorite schemes.
Virtual-table: Objects contain a pointer to a function table. Each method has a fixed offset within the table.
Function-table: There is one table for each method. Objects contain an integer corresponding to the object type that is used as an index in the table.
Switch-statement: Objects contain a type-integer like they do in the function-table scheme. The switch executes the correct function depending on the integer key.
Virtual-table dispatch is used in classed OO languages because the vtable corresponds to a class. It is a data-centric approach because the dispatch mechanism is associated with the data type and not with any specific function type. Method names in the vtable can be overloaded in different struct definitions of the vtable. Extending a copy of the table corresponds well to single inheritance.
The latter two schemes are more similar to each other than they are to the first. They are function-centric because the dispatch mechanism is associated with a function type rather than a data type. An object passed to these dispatchers contains an integer type-id that serves as an index in a dispatch table or a key in a switch statement. Objects in this scheme are unclassed, though there is nothing prohibiting an association on the type integer with a class-like structure. This class-like structure is actually one interpretation of the dispatch table.
Variations tested:
- Virtual-table.
- Function-table at a static address.
- Function-table at a dynamic address.
- Function-table with fix-up subtraction.
- Switch-statment with inline method definitions.
- Switch-statement with few, ordered keys.
- Switch-statement with few, dispersed keys.
- Switch-statement with many, dispersed keys.
- Direct call (for comparison).
The essence of each scheme is in the call instruction. '-S -fverbose-asm' is kind enough to show the names of static addresses.
Virtual table
| call *16(%edx)
The constant 16 corresponds to the offset of the method in the table. %edx holds the address of the table.
Static function table
| call *func_table-3996(,%edx,4)
The constant *func_table is the static offset of the function table. %edx contains the integer corresponding to the object's type. The constant 4 is the size of a pointer on my machine. Finally, 3996 is the index offset multiplied by 4. Index offset would be 0 for a table beginning at type 0, but a subtype might be found in a sub-range of indexes. Rather than build a sparsely populated table for this subtype, a smaller table can be used with a fix-up subtraction computed at compile time.
Dynamic function table
| call *(%edx,%eax,4)
%edx contains the address of the function table. %eax again contains the object's type-id. Fix-up subtractions would obviously need to be computed at run-time. I didn't test this combined with a fix-up subtraction because I consider it pretty useless anyway. I included this test for completeness since a virtual-table is inherently dynamic. Only the method offset is fixed in the virtual-table.
Switch statements
| call compiler black magic
It should be noted that this scheme semantically performs two direct calls for each dynamic method call. The implementation could be placed in the switch to eliminate function call overhead but it may be beneficial in some cases to have separate implementations and treat the switch statement like an interface declaration. In-lining removes the double-call overhead and can be counted on within a compilation unit.
Benchmark Implementation
Most popular benchmark algorithms do not depend on dynamic dispatch. I just did the naive thing and called a function recursively. It can be tricky to fool gcc into making a wheel-spinner that does no real work. For example, it is capable of rearranging the statements of a direct call that is not tail recursive into one that is, then unrolling it, then placing it in-line in the caller.
Timing points are in the code because instrumenting the executable for profiling caused the execution time to double. The key to using gprof might be to turn off instrumentation of the function calls under test and just time the top-level. However, measuring with the real-time clock gives results that are consistent enough to trust.
The Results
Times are in microseconds.
-O0 Classed virtual: 1404442 Function table: 1501014 Function table with subtraction: 1559695 Function table dynamic: 1607794 Switch inline code: 1823262 Function switch: 2612194 Function switch large: 3633052 Function switch dispersed: 3003073 Direct call: 1348344 -O1 Classed virtual: 1506692 Function table: 1506174 Function table with subtraction: 1506311 Function table dynamic: 1506651 Switch inline code: 1311783 Function switch: 2588107 Function switch large: 3026327 Function switch dispersed: 2549603 Direct call: 1368460 -O2 Classed virtual: 1505832 Function table: 1505468 Function table with subtraction: 1505384 Function table dynamic: 1506625 Switch inline code: 1376533 Function switch: 1982367 Function switch large: 2518238 Function switch dispersed: 2046317 Direct call: 1366636 -O3 Classed virtual: 1505480 Function table: 1506294 Function table with subtraction: 1505536 Function table dynamic: 1506019 Switch inline code: 1476872 Function switch: 1476428 Function switch large: 2517948 Function switch dispersed: 1647105 Direct call: 516581 -O3 -fomit-frame-pointer -mtune=native Classed virtual: 1379984 Function table: 1384040 Function table with subtraction: 1380380 Function table dynamic: 1505872 Switch inline code: 1439144 Function switch: 1438757 Function switch large: 2248245 Function switch dispersed: 1506101 Direct call: 509054
These represent a single run. I computed no averages and made no attempt at statistics. However, on repeated runs the times were consistent to within two milliseconds, which is significantly smaller than than the differences between dispatch schemes.
Conclusion, extrapolation, even some guessing and recommendations
Small switch statements do better than large ones, and dispersion of keys has only a small negative effect. For this reason it may be beneficial to reserve switch statements for dispersed keys while using table dispatch for grouped keys. The switch can actually best the table for a small number of keys but then its advantage depends on compiler in-lining or placing implementation code inside the switch. Even if the compiler succeeds in translating the switch to a jump table the double call elimination still depends on in-lining. A macro definition for explicit table dispatch is short and has guaranteed pretty-good performance. It could easily be converted to a switch, or even a switch macro, for the absolute best performance.
One technique might be to treat switch statement/function-table dispatch as one would an interface. Methods like "show", "display", "draw" and other things that usually go in base classes as stubs are good candidates for an interface.
Methods that need to be overloaded for each type definitely benefit from the virtual-table since the virtual-table can contain different types for the method name across different class structures. The advantage of the virtual-table is overloading and inheritance, but if a function is overloaded at the call site then the object type is probably known, and if its type is known then it should be a direct call anyway. Virtual-tables may also have a performance advantage for types that are dynamically created since the table is found through a pointer regardless. The performance of type-indexed table dispatch theoretically relies on having a static table address but my data doesn't show any difference in performance with optimizations turned on. Only -O0 shows any significant difference between method-indexed virtual-tables and different schemes of type-indexed tables.
Large switch statements with dispersed keys perform poorly but this case should not often arise in practice since type-id integers can be assigned sequentially. It is notable that the widest range in performance occurs in switch statements because they give the compiler the most room for optimization. These numbers show that a switch on type-id is the fastest possible dispatch scheme if implementation code is placed in the switch rather than in a separate method. But that's messy. In-lining in -O3 is capable of removing some of the function call overhead and the direct call-switch-call performs slightly better than a function-pointer. The best number here is 200,000,000 calls in 1376533 microseconds for a switch with explicit in-line code compiled with -O2. -O3 brings the performance down to 1476872 microseconds, which is nearly equivalent to the switch that calls a function for each case. The performance is identical in -O3 because of gcc in-lining. With some different tuning parameters the virtual-table and function-table are just as fast.
Personally, I prefer the interface style that jives with the type-indexed schemes. They are interchangeable, don't need a class, and perform as well as virtual-tables. The style lends itself more to multiple interface inheritance, similar to Haskell type-classes with monomorphism turned off. If a type (which is an integer index) has interfaces A and B (which are table or switch dispatched functions), then it may implement C (which is dispatched the same way).
This excellent style of multiple inheritance can also be done in C++ with one pure virtual base class for each set of functions that comprise an interface. But because C++ uses vtables, each object must keep a pointer for every interface from which it derives. I can't help but think a type-id implementation would make more sense in this case too. Tnen each object would have exactly one type-id and every pure virtual base class would be a table of implementations for those type-ids. Maybe I'm ignoring practical issues like linking and horribly sparse tables, but what about the practical issue of keeping objects small? Virtual tables yield big objects and small tables. Type-ids yield big tables and small objects. I ran this same test with C++ and the performance matched the vtable here. Automatic casting to the interface reference didn't appear to affect performance.
Techniques for local viewing with wget
December 20th, 2008
Wget is a good way to collect interesting websites or HTML e-books for off-line reading. The program is capable of pretty much anything and it took me some trial and error to get reliable results. Some hosts have unfavorable robots.txt files or send different results depending on the user-agent. I've even seen some hosts configured to deny the wget user-agent. After some iteration I have found a good set of options that just works all the time.
wget -rSNpk -np --execute robots=off -U "Mozilla/5.001 (windows; U; NT4.0; en-us) Gecko/25250101"
The above line contains the following options in -rSNpk -np. The rest of the line just tells wget to ignore robots.txt and to send a bogus user-agent.
- -r recursive fetching
- -S preserve server modified date
- -N download only if file on server is newer than local copy
- -p fetch page requisites (images, sounds, stylesheets)
- -k convert links for local viewing
- -np no parent, recurses only on siblings and children of a url
The --follow-ftp option is also useful for some sites having ftp assets, which is common for pdf and video.
If you don't want to swamp the host there are the following options.
- -w
wait n seconds between fetches - --random-wait modify wait time by 50% to 150%
The following line is in my ~/.bashrc
alias wgetr="wget -rSNpk -np --execute robots=off -U \"Mozilla/5.001 (windows; U; NT4.0; en-us) Gecko/25250101\" $@"
Usage: wgetr http://example.com/ebook-with-no-gzipped-download-link
And that is how I use wget. If it's worth reading it's worth saving.
Vala is Awesome
December 11th, 2008
The GUI Dilemma
Linux has many language implementations but I keep finding myself driven to C by quality documentation and faithful implementations. Python, Ruby, and Scheme are all great but docs for bindings are second-hand and I usually need to pull out the original library reference or look at C headers and test-cases to accomplish anything.
If I want to port to the maemo platform I have to port the bindings too. Just more version hell.
On top of that there is interpreter lock with internal threads and that isn't good for the GUI. Loading a GtkListStore is already slow enough when calling from C but doing it in an interpreted language means an inner loop with additional marshaling. Database extensions should also be written as efficiently as possible because that makes them more flexible as I don't have to tiptoe around them in SQL; worrying whether my slowness is getting called 10 or 10e6 times per query. Then there's callbacks, like for sorting, which are called nlogn times or worse. If I'm writing asynchronous IO, ListModel loading, database extensions, and sort callbacks in C then there's very little left to do in an interpreted HLL.
I hate GObject C but I like GObject enough to wish I had used it for some things that are slowly turning into their own private spaghetti hell. Refactoring creates even more opportunities for error and is time consuming. C is hard, let's go shopping :)
C++ would be a good option if I had a much higher IQ. I can use existing classes but writing a new class without memory leaks, using it properly with exceptions, and looking out for excessive copying is a mental exercise in itself. That's actually a languages strength, lots of meaning in a line, but it's not an abstraction as much as it is a complex macro expansion. It's a fun language but it doesn't offer the blissful ignorance I often want.
Introducing Vala
With Vala the blissful ignorance is there for the taking, up to a point of course. It is a modern but slightly crippled language that steals as much as possible from C#. It has all the OO features of GObject, including singe inheritance, multiple interfaces, runtime binding, and dynamic properties. Destructors and constructors are supported along with private/protected/public members. There is also a limited "compact" class that avoids GObject for better performance. Structs and types built on machine words like int, float, and bool do not have OO features and have an exact correspondence to C. There is a string type built on GString that supports some useful operators like + and +=. Type inference means variables can be declared simply with the "var" keyword. The type-system also differentiates between nullable and non-nullable types and checks GError exceptions at runtime. Garbage collection is accomplished via reference counting, which is good enough for most things. Vala supports generics with the familiar template-like syntax. All generics appear to be implemented with gpointer, i.e. (void *), instead of creating new code and structures for each instantiated type. For example a Point2<int> p = {1,2} would create a struct containing two gpointers. Function delegates can be defined inline and look like a lambda. Currently, only formal parameters of the lambda may appear in the body. Vala accepts full lexical closures syntactically but the generated C contains undeclared identifiers and does not compile. Vala will most likely implement ref-counted closures in the future via GClosure, or so I hope.
The language compiles through C and anyone familiar with GObject should be able to read the C output to easily figure out what's going on. I wouldn't hesitate to use a Vala library from C because it's really just GObject under the hood. Bindings are easily implemented in a separate "vapi" file. There is no documentation for vapi at the moment but it really doesn't need much. Marshaling is delegated to GObject at runtime and calling GObject code from Vala doesn't cost any more than calling from C. The whole language is actually syntax sugar for C. It's C++ reinvented with the benefit of C# and Java in the rear-view mirror.
GObject has a high runtime cost but the Vala designers have created some very useful pockets in the type system to mitigate that issue. Vtable lookup always occurs for interface methods, unfortunately even when the concrete type is known at compile time. Inherited methods are called statically through upcasting so better performance is possible by restricting OO usage to compact classes and inheritance-only method resolution. The pointer overhead in generic structures would probably offset any performance increase from static method binding unless it is used carefully. Unrestricted use of generics would imply using them in interface constraints and those entail virtual method calls anyway. The language also doesn't leverage stack allocation for objects like C++ so instantiation requires heap allocation. Structs have access-controlled members and are normally stack allocated but copy constructors and destructors are still generated for structs to support full-object members. The compiler currently accepts inheritance and interface syntax for struct declarations but ignores it when generating code.
The roadmap is set for a 1.0 release in March 2009; fingers crossed. Vala is promising because it's conceptually simple, as portable as glib, has decent performance, and plays well with C in both directions.
PS. I should warn the reader that I just discovered Vala yesterday and my knowledge of it is limited to examining the C output of the version 0.5.2 compiler. Some of this info is probably wrong so this article is As-Is, No Warranty. However, I'd appreciate a comment if I failed to understand something about Vala.
The Port Authority Draft
December 2nd, 2008
Yesterday I spoke with a man whose supposed infraction of Port Authority rules may lead to a personal fine of $1000. His crime was failing to challenge an under-cover officer's undisplayed ID in a secured area. To tell this story while protecting the innocent I'll just call him Joe Pilot and say he works for a made-up Westwind Airlines. The undercover officer is Decoy Dan.
Decoy Dan approached Joe Pilot in a hallway of a secured area and started a short conversation. After a few seconds of this Dan indicated that Joe should come with him because Joe had done something wrong. Joe obliged and the pair walked a few steps to the chief pilot's office where Joe learned the extent of his liability.
The secured area I'm referring to is one of offices, filing cabinets, desks, lounge chairs, vending machines, lockers, and break rooms. It's not a busy ramp where alertness is required for physical safety but a place where crew go to print paperwork for their next flight, relax, or take a nap. A terrorist would enjoy the area for its access to aircraft so security is very important. In this area people should voluntarily raise awareness to abnormal situations for the same reason they bring any other safety related issues to immediate attention. The issue here is not whether Joe should have challenged for ID but whether it was his legal duty.
Joe was allowed in the secured area because he had an ID badge issued by Westwind Airlines. The terms and duties of his employment with Westwind were governed solely by his union contract and there was no requirement therein for Joe to challenge undisplayed ID. Joe wasn't even on paid company time during the infraction. The Port Authority issued badges to vendors and other airport employees but not to Joe. Joe did not have a Port Authority ID, which is the one Decoy Dan should have been wearing when he spoke to Joe. Joe had only a company ID and was required to challenge a Port Authority officer for failure to display a Port Authority ID.
Joe's infraction is one of inaction. He didn't DO something illegal but FAILED TO DO something supposedly required of him. Pilots have grave responsibility and have agreed to perform certain duties in accordance with their company employment and FAA certification. Joe can be held responsible for e.g. failing to check fuel levels before departure by both the company and the FAA. He has studied his duties because he is a professional and he performs them voluntarily because he is a free man who agreed to perform them. The FAA certificate bearing his signature is proof of that agreement.
Joe has never had an agreement with the Port Authority and yet they are holding him responsible for failure to notice and enforce rule violations committed by their officers. Free people can do anything that does not infringe on the rights of others. Doing nothing does not infringe on the rights of others so free people are free to do nothing. If the Port Authority can conscript Joe into their service then Joe is not free. This is a back-door draft of formerly free people into government service.
Why Google Apps Fail
July 15th, 2008
Google Apps is(are) the new MS Office complete with spreadsheet, slide presenter, database, and word processor. They all suck. Commonly cited reasons for failure are that the browser is not an OS, Javascript lacks support for concurrency, Javascript is slow, businesses are slow to adapt to new technology, community authorship is already solved by VCS and wikis, etc. Here’s the real reason they fail: fighting the last war. Word processors and spreadsheets are generic, where “generic” carries the same negative connotation as when applied to performance art.
Google shouldn’t be trying to make generic apps easier to use on the web. Email, IRC, IM, wikis, forums, and social bookmarking have an evolved interface balancing generality with complexity. They are also not stand alone programs that can have the network part removed like a word processor. Even if all the technical browser/script problems are solved, what will Google Apps offer other than a plethora of features bolted on to something resembling a wiki? It’s generic.
Features can increase generality, but at some level of generality the competing technology becomes Sqlite, Linux, or Java; not MS Word. I’ve witnessed the humor of a Salesforce tech-support conference call. My client was using a form that posted to Salesforce and was trying to add some work-flow features on the Salesforce end. What I heard astounded me, the client was getting a lesson in scripting from the tech. I left the call early, glad my part was limited to creating the form. A solution can go in two directions as it becomes more general; more abstract, or more complex. MS Word and Powerpoint embrace complexity. Programming languages lean toward abstraction. Either way, generic solutions are always harder to use.
The MS Office suite thrived because it made it easy to share. Embrace, extend, extinguish. One app to open them all! The complexity was necessary for generality, and generality was necessary for sharing. On the isolated PC there wasn’t room for a special version of Powerpoint for teaching with another for pitching sales. Word had to handle letters, resumes, and instruction manuals, in formats including HTML, text, and binary. It had to interface with Access and embed Excel documents, and each of those programs had to share well with others in the suite. It was a very capable one-size-fits-all solution that was very complex as a result.
With the web offering effectively unlimited storage on top of easy distribution and sharing, there is no longer a need for one-size-fits-all suites. New apps can depart from the generic view of the suite and approach problems directly. There should not be a Powerpoint of the Web . Instead, applications should specialize so that one for e.g. teaching aircraft systems or training sales reps will bundle a tailored likeness of Powerpoint. Slides in this new hypothetical software might pull facts from manuals or link to simulations, each of which is another specialized application, reiterating the importance of sharing. Thus, The Web
Google Apps solve the problem of sharing by offering a uniform API (so 1990), on the web (so 2000). In contrast the new application suite will have as many APIs as there are applications, and as many applications as there are problems to solve. Google Apps are generic and lame.
Sqlpilot
April 15th, 2008
My aviation logbook project, Sqlpilot, recently become usable (for me). I was able to turn my old data into CSV with plenty of grep, sed, awk, sql, manual labor, trial and error, and luck. Sqlpilot is a C program linking to gtk and sqlite. Using a relational database feels like the right way to manage a logbook and I now have a whole new view of my flight log. I've been querying things like average leg time and distance for specific aircraft, number of days with over eight hours of flying, number of approaches flown grouped by month, total time in each aircraft and type, and other interesting trivial things that I would have never known had I not started this project.
Read the rest of this entryBeans worth Blogging About
March 3rd, 2008
Tara and I frequent a Thai Restaurant about a half mile from our apartment. Without too much thought I placed an order for something on the menu called Sator Shrimp since I like shrimp and spice doesn’t bother me. The waiter asked if I had ever had sator before and warned that the dish had a strong smell. That piqued my interest so I stuck with the order. The dish wreaked of odorized propane gas and the flavor of sator defies description. I didn’t know a plant could taste like that even though I ate things like pine needles and radish leaves as a kid. I finished the dish because I was extremely entertained that someone somewhere actually planted sator beans with the intent of selling them as food. Each bite was like the culinary equivalent of the Jerry Springer Show. After the beans were in my stomach and the sensory-masking effect of curry wore off I began to notice the smell again. It was my breath; onions are to sator what tictacs are to onions.
Googling after dinner I found that sator (parkia speciosa) is informally know as a Stink Bean
I can’t even believe a plant like sator is legal to grow in the USA considering growing relatively benign plants like Cannabis can win their owner a prison sentence. We need laws to protect our children from sator now :)
"Missing the point", Misses the Point!
February 7th, 2008
If there was ever a phrase which should be banned from all discourse it is “missing the point”. Missing the point means making an irrelevant conclusion. It’s similar to a non-sequitur with emphasis on the conclusion rather than the evidence. Instead of saying a conclusion is wrong because the evidence is irrelevant (non sequitur – does not follow), “missing the point” directly attacks the conclusion as irrelevant and therefore wrong.
Many Internet discussions have no point and therefore none to miss. Good discussions have many points and that’s why most comment systems are threaded – so different points can be clearly discussed! Don’t tell me I’m missing the point because I introduce a new spin on things. Instead, be a genius and fork the thread. If you disagree then say so, but how could you disagree if I was truly missing the point? If you rebut irrelevance with anything other than an explanation of why something is irrelevant then your clever rebuttal is non-sequitur since the chain of logic is broken. This is what downmods are for. Use them. “You’re missing the point”, is just a red flag that means irrelevant, obvious, or arrogant statements follow.
Which brings me to arrogance. By claiming that I am missing the point you have implied that there is some “one true” point that I have missed. How is that even possible? Does each cause have one and only one effect, and vice versa? It’s nearly the definition of simple-mindedness. Like thought police you seek to limit the scope of discussion to protect the logical purity of your narrow, self-idolizing views though mindlessly repeated idioms. It’s doubleplus ungood for real discussion.
Think I’m missing the point or full of shit? Consider that Google claims over three times the number of hits for missing the point then for the overused phrases full of shit and full of crap combined. Please stop polluting discussions with this trash.
Haskell Music
January 22nd, 2008
As part of my effort to seek enlightenment through Haskell I’ve made some music. It’s actually sort of neat creating a waveform that when played through a DA resembles something other than white noise. This isn’t controlling a sequencer – it’s just composing functions to make make a sound representation. It’s a lot like naive ray tracing where all objects are considered for each pixel in that for each sample I sum the waveforms for all notes, many of which are zero since a note only plays for a short duration and is otherwise silent.
Notes are made by transforming a sound frequency Signal (Double -> Double) with pitch and amplitude Shifters (Signal -> Signal). For the note envelope I create a signal that represents amplitude and modulate the sound signal with the amp combinator, which is a Modulator (Signal -> Signal -> Signal).
One thing missing from this implementation is the ability to write (signal = signal1 + signal2). I now would write (signal t = signal1 t + signal2 t,) since a signal is a function over time. mauke in #haskell (irc.freenode.net) was helpful but I still don’t understand why some things work the way they do so I chose not to write a (+) instance for signals until I understand it better. The following will play a few measures of Mozart’s something something as I remember it. I forgot what it’s called but it’s in C and it’s popular.
Here’s an ogg vorbis of the output: mozart.ogg
And the illiterate Haskell.
-- Compile and listen as follows
-- ghc -o mozart mozart.hs && ./mozart | mplayer -v -rawaudio rate=16000:channels=1:samplesize=1 -demuxer rawaudio -
import System.IO
import Data.Char
type Signal = Double -> Double
type Shifter = Signal -> Signal
type Modulator = Signal -> Signal -> Signal
main :: IO ()
main = putStr . toBytes . take 200000 . sample 16000 $ sound
sound :: Signal
sound = ampc 0.35 . shifterSum song . pitchc (440 * hstep ** 3 * 2 * pi) $ wave
song :: [Shifter]
song = zipWith (\e p -> amp e . pitchc p) (lhEnvs ++ rhEnvs) (lhPitches ++ rhPitches)
wave :: Signal
wave = flange (\x -> sin (x * 2)) sin
lhPitches :: [Double]
lhPitches = map (* (1/2)) $ [du,so,me,so,du,so,me,so,re,so,fa,so,du,so,me,so] ++
[du,la,fa,la,du,so,me,so,re,so,fa,so,du,so,me,so]
lhBegins :: [Double]
lhBegins = take 32 $ toTempo [1..]
-- Applies 0.1 second duration to left hand begin times
-- resulting in a list of complete amplitude envelopes
-- for each note.
lhEnvs :: [Signal]
lhEnvs = map (pianoEnv 0.1) lhBegins
rhPitches :: [Double]
rhPitches = [du,me,so,ti/2,du,re,du, la,so,du*2,so,fa,me]
rhBegins :: [Double]
rhBegins = toTempo [1,5,7,9,12,12.5,13, 17,21,23,25,28,29]
rhEnvs :: [Signal]
rhEnvs = map (pianoEnv 0.5) rhBegins
-- attack decay sustain release to resemble a piano
-- apply duration and begin for complete envelope signal
pianoEnv :: Double -> Double -> Signal
pianoEnv = env 0.005 0.05 0.4 0.7
-- eigth note tempo
tempo = 160
toTempo :: [Double] -> [Double]
toTempo ts = map (\t -> 60 * t / tempo) ts
-- Sums list of signal shifters and mutes the original signal
shifterSum :: [Shifter] -> Shifter
shifterSum xs = foldr (shifterAdd) (const . const 0) xs
shifterAdd :: Shifter -> Shifter -> Shifter
shifterAdd a b input t = a input t + b input t
-- 1 b
-- / \c_____d
-- / \
-- 0 ___a/ \e___ Makes an amplitude envelope for a note
--
-- Will div by zero in some cases.
env :: Double -> Double -> Double -> Double -> Double -> Double -> Signal
env attack decay sustain release duration begin t
| t < a || t >= e = 0
| t < b = (t - a) / attack
| t < c = 1 - (1 - sustain) * (t - b) / decay
| t < d = sustain
| t < e = sustain - sustain * (t - d) / release
where a = begin
b = a + attack
c = b + decay
d = c + duration
e = d + release
sample :: Double -> Signal -> [Double]
sample rate signal = [signal (t / rate) | t <- [0..]]
-- yuck
toBytes :: [Double] -> [Char]
toBytes = fmap $ chr . clamp 0 255 . (\n -> truncate $ (n + 1) * 127)
clamp min max x
| x < min = min
| x > max = max
| otherwise = x
pitchc :: Double -> Signal -> Signal
pitchc mult input t = input (t * mult)
ampc :: Double -> Signal -> Signal
ampc mult input t = mult * (input t)
amp :: Modulator
amp control input t = (control t) * (input t)
-- only works for control where d/dt = 0
pitch :: Modulator
pitch control input t = input (t * control t)
flange :: Modulator
flange ff w t = w (t + ff t)
hstep = 2 ** (1/12)
du = hstep ** 0
re = hstep ** 2
me = hstep ** 4
fa = hstep ** 5
so = hstep ** 7
la = hstep ** 9
ti = hstep ** 11
Tara's Blog
January 9th, 2008
Tara, my wife, has been maintaining her personal blog primarily with php for templating and no database. Recently she had the desire to add RSS feeds but since her pages and articles consited of only php files we would need to either scrape the feed from the pages or start using some real blog software. I have been using mephisto so I set that up for her. After we both had done considerable work on templating and transfering content she decided to just retemplate her php setup and worry about RSS later. I think it was a sound decision. After all, editing in the browser sucks. She’s been using vim but now prefers the aquamacs style of emacs since I introduced her to that. What can I say? A blog should be nothing more than a directory full of files that gets scanned into an index for display via html or rss. The metadata in liunx is a bit sparse since there is no creation date on files – just accessed and modified time. Publishing, tagging, and categorization could be handled through symlinks. Search could be a done via grep and cgi but I’m a little worried about escaping the search string correctly. Comments can be an entirely seperate system for all I care. If only linux wasn’t so tantilizingly close to a multiuser CMS/Blog. It’s close – but no cigar.
Six Weeks of Appendicitis
January 9th, 2008
On January 7, 2008 I had my appendix removed more than six weeks after initial symptoms.
I began feeling fatigued during a trip on Nov. 22nd. With symptoms of fever, extreme fatigue, and abdominal pain I called in sick and went home on the 24th. On the 26th I went to a primary care provider and was diagnosed with hematuria caused by a possible kidney infection or stone. I left with a prescription for seven days of steroids and ten days of antibiotics. Ten days later I still felt ill so I returned to the clinic where I again tested positive for hematuria and got a referral to a urologist. The urologist referred me to a CT scan where finally, on the 10th of December, I found the cause of my sickness to be an enlarged appendix. The urologist referred me back to primary care where I received a referral to a surgeon. The surgeon reviewed the CT scan and decided to remove the appendix but advised that since my condition was improving it would be best to allow some healing to occur before cutting. He prescribed some antibiotics and said it would be okay to work but agreed it would be best to consult an aviation medical examiner. The aviation doctor also said that I could work until surgery but cautioned me that I should not work with pain since it was a distraction. Since I was pain free for three days I returned to work on the 17th of December but the altitude changes and turbulence caused my abdominal pain to return. As should be expected the aviation doctor was right, pain is really distracting. I called in sick again and decided to wait until I had recovered from surgery to return to work. The surgeon did a great job and I have had less pain during recovery than I did during much of December. I don’t need pain medication but I have been using one dose at night to sleep through the minor discomfort of three incisions in my stomach. Finally, almost two months after beginning sick leave I will be fit to return to work. I have used the majority of my sick bank and filed for FMLA. What should have caused me to miss three weeks of work turned in to seven and a half. The hospital staff, surgeon, urologist, and CT scan folks were excellent and I have great respect for them and their profession.
As for so-called primary care, this is not the health care I grew up with and I don’t really know where to point my finger. The primary care PAC and her doctor focused on kidney issues due to hematuria and assumed the abdominal pain was associated. Blood and urine were taken for additional testing but the blood results took days to complete. Blood tests confirmed I had an infection of some sort. There was no X-ray, CT, ultrasound, MRI, or any imaging in the office. Getting imaging done takes a referral and an appointment several days away. A CT scan would have removed the possibility of a kidney infection or stone. I can only assume that if there was imaging equipment in the office I would have been referred to a surgeon two weeks earlier than I was, maybe even had my appendix removed that same day. Since it takes three to five days to schedule a CT scan it would seem reasonable to begin taking drugs for the most likely problem until the scan could be completed. Even then, I would most likely need a specialist referral and that can take even longer to schedule than a scan. Why can’t I go to the doctor and get some real tests done so I can get a diagnosis? Do I blame the system or just assume I chose bad primary care? This isn’t the first clinic I have found in the area. I have been to a few and shopped around. They are all in professional buildings and are staffed by approximately ten doctors and nurses. They have a microscope and a stack of magazines. Any real tests require a referral. I personally think primary care has become nothing more than a sales outlet for pharmaceuticals.
While at the hospital I told the nurse about my referral saga and asked if she knew of a primary care clinic that had at least an X-ray machine. She advised that she was not allowed to give recommendations. Fair enough, but she also said the care I received seemed standard. Usually primary care, the place I go with symptoms, is a professional building with very limited equipment. What are these places? All they can do is prescribe drugs and when I’m sick I may need more than drugs. The hospital is where the real care is but unfortunately I don’t qualify for that clinic since I actually have insurance and I’m not a senior citizen. In the end I paid more in co-pays than an emergency room would have cost. My profession as an airline pilot is also incompatible with referrals and waiting since I am essentially grounded until I know what’s wrong. I can’t just go to work while I wait for test results for documented symptoms. I am required to have a medical exam every six months and it is clear that going to work sick is illegal, stupid, and a willful violation of the law. Despite the cost I am considering skipping the bullshit and going to a real hospital with real equipment next time I have symptoms.
This leads to billing. I have great insurance. It’s a 90/10 plan with no deductible and a reasonable out-of-pocket maximum. I chose this plan over 100% coverage because even with my surgery the total cost in premiums and coinsurance is about equal to the cost of 100% coverage. These are the benefits of working for a good company and being part of a strong union like ALPA. I lost no pay since I had time in my sick bank and FMLA will keep me in good standing with my employer. This is to say, I am not forgetting to count my blessings.
I do, however, have some issues with the billing which make me worry for the day when I have no insurance. A typical test for blood or urine might be billed at six times what the insurance company actually pays. A $380 lab test gets covered at $60 by BCBS. When I asked how much my CT scan would cost I was told $2000. They billed BCBS for $850 and BCBS paid around $500. My bills all share this trait with lab work having by far the greatest discrepancy between what is billed vs. paid. Before the surgery I tried to find out what it would cost but no one could tell me. I signed that I would pay the bill if the insurance company denied my claim without a clue what it would cost. I know it depends on the resources and time used. If I had to stay additional nights in the hospital or have more surgery and blood transfusions it would cost more. Still, why can’t I get an itemized estimate ahead of time? An accurate estimate would be nice. Don’t tell me it’s going to cost $30,000 and then bill the insurance for $6500 while getting paid $4000. This is exactly what would have happened so I didn’t really mind not having an itemized bill.
I have it better than most people in America. Many folks pay larger premiums and have per-person deductibles which for a family can lead to terrible cost. Others have no insurance. Do they pay the full 600% markup on lab work? Primary care is a WTF. Billing is a WTF. At least I am alive. Thanks also to my wife for helping me with the innumerable pains and annoyances that happen during illness.
The Best Tutorial - Write Yourself a Scheme in 48 Hours
December 26th, 2007
Write yourself a Scheme in 48 Hours
This is the most excited I’ve been since I learned how to make a character bounce around the screen on my C64! Learning a new programming style is hard: big programs are difficult to understand and small programs have too little to tweak. How do I learn from a ten line tutorial or a one-hundred line program? The ten line tutorial doesn’t do anything interesting and forces me to write new code to grow. OTOH, one-hundred lines of Haskell usually do something neat but I can’t begin to untangle how. For everyone there is a threshold of complexity, the understanding of which enables creating more complex things. Once this threshold is achieved a person can bootstrap their learning as an autodidact. Below it there is neither enough knowledge to guide their study or test their knowledge for correctness.
My capacity for understanding is often far lower than the bootstrapping threshold and my learning stalls as I fumble through tutorials gaining one small bit of knowledge without correlation until one day things begin to click into place. I then wonder how I learned in eight hours what had stumped me for eight months and feel profound appreciation for the wizards that understood it first. It’s like I was blind and they could see, and now through some miracle I also see. It’s real sight too, not just a description in words but the real sunrise seen for the first time by the formerly blind. In this case the misfitting pieces were the static algebraic types, monads, type classes, currying, and lazy evaluation of Haskell. It’s quite a bit to swallow just as the more familiar loops, conditional statements, functions, and variables once were. Many of these things are interdependent and cannot be understood separately. Jonathan Tang begins small and works from the ground up to a larger program, explaining each change so every line’s purpose is thoroughly understood. The culmination is a very small but capable scheme interpreter that is larger than what I would have understood without my building it. It is a perfect demonstration of the building-block technique of instruction I learned and used as a flight instructor.
Mr. Tang put the pieces together concisely. Wow.
My Documents
December 26th, 2007
Xmonad
December 13th, 2007
Xmonad is an awesome window manager and these are my complements as a fanatical user. The thing I love about Xmonad is that it just seems to get everything right. Wmii, my first favorite tiling WM, really got me interested and I found no fault with it until I used Xmonad.
Internally Xmonad manages focus with a zipper data structure. Though there are more naive approaches used in early versions it’s clear from maintainer Don Stewart’s blog that a lot of thought went in to my sanity as a user. The sorted order provided by the zipper allows for completely automatic management of my windows. For me, the order reduces my workspace to essentially one dimension. In Wmii I used vim key-bindings to move focus up/down/left/right. In Xmonad I use only two keys for this. In every other window manager Alt+Tab is a total pain due to the random order of the windows or the fact that they need to be manually sorted. Xmonad always inserts and deletes windows in a way which preserves order as if I were inserting or deleting lines from a text file. Better, Xmonad can be extended with, among other things, algorithms to arrange windows based on this order. There are tabbed, grid, and circular layouts to name a few. One interesting extension even arranges windows in a Fibonacci spiral.
There’s plenty of fud floating around about the inextensibility of purely functional programs but Xmonad proves otherwise, at least for Haskell’s case. I feel like a dog watching TV when viewing the source but I do know this; the extensions manage a variety of state and the code is concise. Oh, and the whole thing runs in a memory image a little larger than an instance of bash.
Special thanks to Spencer Janssen for authoring the project. Xmonad is doing everything just right so my Archlinux machine is polished like a Macintosh, only more useful.
Arch Linux vs Ubuntu
November 17th, 2007
Yes! Arch is great. For more detail read on.
Arch's Appeal
The main difference between Arch and Unbuntu is that Arch is designed to be molded whereas Ubuntu is a complete desktop/server distro. Like Ubuntu, most things were configured and worked upon install. Unlike Ubuntu, Arch does not have a default desktop environment although XFCE4 could be considered well supported. Arch will appeal to users who wish to start with a minimal system and a package manager, adding bit by bit until the system is tweaked to their desire.
Ubuntu's Appeal
Ubuntu is for those who just don't want to mess with it - giving users the choice of a server, or a Gnome / KDE / XFCE desktop. There is also a minimal (alternate) Ubuntu installer for those who want more control. I wont say Ubuntu 'wins' here or anywhere because it's apples and oranges. Yes - Arch vs. Ubuntu is a stupid comparison but if you're like me and you can't help but type X vs. Y into Google before doing anything then maybe identifying some differences isn't so bad. In short, Arch maintains bleeding-edge, occasionally broken, packages with no release cycle whereas Ubuntu needs upgrading (breaking) every six months. Ubuntu is good software with target markets. Arch is good software.
Package Management
Arch uses a rolling release cycle where major releases consist of a snapshot. For a personal computer, avoiding Ubuntu's six month upgrade cycle is a definite benefit. On the other hand it could cause breakage occasionally, which is why I still prefer Ubuntu (LTS) for my server. Arch packages tend to be more bleeding-edge from what I can tell browsing the repository. For example, the packaged version of GHC in Ubuntu 7.10 is 6.6.1 while Arch will install 6.8.1.
Pacman, the Arch package manager, is similar to apt. One thing I really like is that headers are bundled with library binaries. This makes sense since headers have a tight coupling to the code they describe. They can also be used as documentation when man pages are weak. With Ubuntu I had the option of not installing headers but that proved to be sort of a PITA when compiling or building a new development system. Ruby gems also uses gcc occasionally and it's nice to avoid the search for *-dev packages. pacman -S imagemagick && gem install rmagick just worked.
Post Install
Everything is installed, configured, and working as per the normal Ubuntu setup. Arch requires a few extra steps to get a desktop environment installed. Here's a few examples.
Xorg
Unfortunately I had to configure X. I say, 'unfortunately', because I hate configuring X. Best to just install Ubuntu on another partition and copy the xorg.conf. Currently I'm using the open-source ATI drivers since I couldn't get the proprietary ones to install properly. I'll be working on that later.
Sound
Running alsaconf asked a few questions and my sound card worked. Easy.
Suspend and Resume
Suspend and resume with swap and ram work great using the pm-utils package. I had to configure the resume scripts to run alsactl restore to get sound working after a restore but other than that it was configured perfectly upon install.
CPU Frequency Scaling
Ubuntu Forums had a great post on this topic. Since it's dealing with the kernel it works on Arch too. http://ubuntuforums.org/showthread.php?t=248867
In Total
I'll be using Arch for the foreseeable future, maybe even contributing if I'm ever capable of fixing something. The documentation on their wiki is outstanding and the community has momentum. In general, Ubuntu is great for the automated installation and configuration of everything to include the kitchen sink. Arch is great for a lightweight and fast system with a rolling release cycle and bleeding-edge software.