Þ   briarpig  » log  » aug07

r6rs ratified ¶

     As LtU reports, Scheme's new spec for R6RS has been validated by a vote of 2/3rds. I didn't vote (and I'm nobody) but I sided with the No vote camp based on extra complexity and spec growth. My Lathe Scheme will be a boutique language: it won't support R6RS. I'll target R4RS first, then maybe R5RS.

stats reprints ¶

     I'm really busy, and folks are interested in stats, so all the rest of today's post consists entirely of reprints from my website several years ago on topics of statistics and gaussian (normal) pseudo random distributions. I'll reformat old content slightly so it doesn't vary too much from style here. But clarity might suffer.

boxmuller ¶

     The following section presents the original 11mar2001 material I found on BoxMuller used for gaussian distributions. After than I'll include the C++ class I wrote years ago to use this more easily. Why should you care about generating gaussian distributions? Since you can generate pseudo random numbers with a particular average and standard deviation, you can directly test statistics code I show later, to see if it does averages and standard deviations.

thank you, everett f. carter jr (11mar2001) @

     Friday I found a fabulous piece of code I present below. I bet a fair number of coders will want to use this some day. You can see the original ftp URL in the first C style comment. I found a web page on "Generating Gaussian Random Numbers". This page is at http://www.taygeta.com/random/gaussian.html.

     So you ask yourself, why was I interested in this bit of code? Because I'm writing an elaborate simulation unit test at work. To test my current project, I need some normal distributions. I spent three days writing this highly multi-threaded, um, thing. Now I'm writing a complex and highly multi-threaded unit test.

     For my unit test to be realistic, I need normal bell curve patterns. These are also called Gaussian distributions. Okay, same thing. (You in the back, wake up! Or I'll throw this chalk eraser.) But I couldn't remember how to get them, for the life of me. I knew there was a way, from dabbling in simulation years ago.

     Of course I've a usual pseudo random number generator in hand. And a version of this generating uniform distributions in [0..1]. But how in the world do get a Guassian distribution from this? I started a web search Thursday afternoon and hit gold Friday. The page I cite above had just exactly what I needed. Huzzah.

     One of the math guys at work is very charmed by how this works. If you're a math head, you might think this is pretty interesting. But if you're not, then you probably only care about what it does. I barely understand it myself, since the level of math is past me. There's no possibility at all you'll get it from the code below.

     If you want explanation, you'll need to see relevant web pages. All I can tell you is how I tested this to verify it works okay. Maybe later I'll post a unit test that generates the histograms. I made an array of a hundred bins, and filled them with results. I gave box_muller() a mean of 35.0, standard deviation 10.0. Lo and behold, a bell curve distribution is exactly what I get.

     Of course, I had to modify the code below to fit in my context. I used my own uniform distribution function taking explicit seeds. The I restructured the code in C++ to avoid the static variables. Then I jiggered my usage so it's multi-thread safe for each driver. Of course I'm using double and not float, so don't nag me.

     Later I'll probably write a Mithril or Ytterbium version of this. Oh yes, one more thing. This code here goes wickedly fast! One microsecond per generated pseudo random Gaussian number. This is important when you write a multi-threaded stress test.

normal ¶

     Below is the version of the C++ class I published on 24nov2005, with the class named Normal (instead of the usual BoxMuller name I use in practice).

     Here's a C++ rewrite of the C version of the box-muller transformation. It returns a sequence of pseudo random floating point numbers with average value equal to mean and standard deviation equal to sdev when these parameters are passed to the constructor. If you plot return values from next(), they form a bell curve distributed normally around mean.

variance ¶

     Below is material on variance and standard deviation I published on 25nov2005. Let's start with the rationale for why it works, followed by the actual code. At the end is a presentation on using BoxMuller in a unit test.

problem ¶

     You want to summarize a large number of numeric values as some kind of "digest" characterizing the population as a whole. The space cost should be constant, no matter how large the population. (You plan to keep a large number of such digests — say to summarize memory block sizes or ages associated with each backtrace that allocates — so size is a concern.) Merely counting the population is a first step. But this tells you little about the actual values. Besides remembering the min and max values seen, what else can you do in order to get a handle on population variability?

insight ¶

     The field of statistics provides tools for problems like this. The average and standard deviation for a population is a good digest summarizing a set of numeric observations. A little research tells you standard deviation is just the square root of variance. And you can calculate the variance of a population without having the entire population still around for analysis. All you need to calculate variance is three values (with constant size):

• N: the size of the population
• sum: the total every member added together
• sum of squares: the sum of each member squared

     The definition of variance is the sum of terms (x_i - μ)² divided by (N-1), where μ is the average value (aka the mean). If you expand the squared term by simple multiplication into x_i² - 2x_iμ + μ², you find you can remove the awkward x_i component because x_iμ is equal to μ² in the average case, looking at all terms in the summation. So (-2x_iμ + μ²) → -μ², and variance is just (Σx_i²-Σμ²) /(N-1). Obviously since you can't divide by zero, this only makes sense for values of N over one. (A single value doesn't vary.)

statistic ¶

     Here's the trivial code for calculating variance on a single statistic. This class would also be the right place to keep min and max values if wanted. And add() should be overloaded to accept each type of numeric input that is normally observed.

recipe ¶

     Everything hairy about calculating variance occurs in the algebraic simplification of the summed terms noted above. The code listed [above] is simple. But how can you tell it's correct? And can variance ever be negative? (You can't take the square root of a negative value when calculating the standard deviation.)

     This is where the boxmuller code for generating normal distributions comes in handy. The boxmuller object (class Normal) takes the mean and standard deviation as input arguments, and then generates a population having these attributes. So a good unit test can use class Normal to generate a population, and then use class Statistic to summarize this population, and see if the generated population actually has the input attributes. (See the unit test output below.)

testing ¶

     The rest of this column is about testing the class above. How would you go about verifying that it actually captures the variance for a population of numbers? Two plausible ways will actually reinforce each other. The unit test does both:

• use boxmuller to generate the sample population
• plot the results on a graph to see a normal distribution

     The rest of this column explains the code in unit test boxmuller.cpp, working backwards from main() to create the output shown in the right column.

     The unit test merely calls variance_examples(), which uses class Normal to generate a gaussian distribution, and class Statistic to find and verify the expected mean and standard deviation. A stars() printing helper appears in the column at right; the rest of this colum is the guts of variance_examples().

     Those magic numbers 2048 and 30 just control the size and shape of the graph plotted in the output. The 2048 gaussian points are grouped in 30 different histogram buckets. The hill array is the bell-shaped curve histogram, and must be initialized to zero since we'll increment these for each hit that occurs.

     The gaussian distribution generator is nm, using (arbitrary) starting seed 31555, mean (average) value 1500.0, and standard deviation 450.0. Instance st is the statistic used to create a digest of the points generated by nm. (You can see in the final output of the unit test, st will see an average value of 1502.1 and an observed standard deviation of 447.3, which seems close to me.)

     This loop generates all the unit test's actual data. Expression ++nm generates the next pseudo random gaussian point, using Normal::operator++(), and this point goes in the next array slot. (Which we never use; if you wanted to reckon variance another way, this is where you'd get the data.) The statistic observes each point via st.add(point), and then the point is aggregated in a histogram bucket by expression ++hill[point / 100.0]; but we drop hits that fall outside the histogram array when j>=LEN (which is unlikely but possible).

     Dividing point by 100.0 is arbitrary, but has the effect of grouping hits in multiples of 100.0, so the historgram will map range 0.0-3000.0 in 30 histogram buckets.

     This part gets and prints the average value, the standard deviation, and the coefficient of variance (a scale-free measure of variability). The first line of the printed output says avg='1502.1' and sd='447.3', which agrees so closely with the inputs to class Normal we might conclude two things:

• the gaussian distribution appears to work correctly, and
• the variance measured by class Statistic looks correct.

     All that remains is the code plotting the histogram so we can visually examine the distribution to see if it looks like the expected bell curve shaped normal distribution, which it does. (Standard deviation drives curve steepness.)

output ¶

     This is the output from a single run of the unit test boxmuller.cpp. The input values used in the test -- as well as the number of observations and summary buckets -- were all tweaked to make a graph that fits reasonably into one column on this page, without taking up too much horizontal or vertical space. The part after each colon is written by stars() above.

printing ¶

     The stars() method just prints a line in the output histogram. (An early version printed one '*' per bucket hit, suggesting the stars name.) The last version saves horizontal space printing hits in groups of four so each byte means one, two, three, or four hits. Glyphs for minus, plus, star, and hash have this many lines.

feel good bulletin ¶

     We interrupt our regularly scheduled broadcast to bring the following message about peace and harmony, and good will to developers.

not slighted ¶

     Kent Beck wrote to Andrew Shebanow about early SUnit work and Andrew posted the letter at history of test frameworks. But I don't know why he says he's sorry I feel slighted, when what I said was, "I have trouble feeling slighted..."

     Doesn't that mean I don't feel slighted? I thought that's what I meant. :-) Maybe the situation seems to imply the opposite of what I say. But let's take me literally at my word — it's simpler.

     At this point I should note Kent Beck's always struck me as a really cool guy — one of those people (and there are very few of them) I admire and envy. So now I feel like a dork: a buzzing fly annoying my betters. D'oh. I'm certain what I wrote must have cost Mr. Beck time to reply, so for this I apologize: I'm sorry I took your time. Thanks for your gracious mail.

     Let this be my final word on the topic: I don't care much about testing, except when I need to test something I wrote myself or suffer more debugging than I would otherwise. (Even saying this much makes me worry someone will think I'm into QA. Nope. I've never done it and never will; not my thing.) Unit testing is something good developers do.

personal mail ¶

     Andrew Shebanow and I exchanged several emails through the briarpig address at gmail, under the rules described on the about page, understanding this is normally for publication on the letters page. But the topic of discussion most of the time was me.

     So it might be a while before I post some of that, seeing what I have left after cutting me out of the picture. A little described what I'm trying to do here: that's the part I want to keep. (Frankly, I can't post something with compliments so positive I'm embarassed to broadcast it. Hmm.)

mentoring ¶

     New folks at work ask me lots of questions and I try not to dodge them, but eventually I have to cut the flow and go back to work, or I'll never check in the code I've been writing. No one complains I'm spending so much time this way: someone has to do it.

     But it's hard with really junior folks, when explanations need explanations, and in the worst case (shudder) the latter also need explaining. For example, today I told our youngest engineer how I add stats to see how many threads on average concurrently run in certain shared sections. That was a long one.

     I count them of course, using atomic integers (ie threadsafe integers), sampling the thread counts in shared sections. Pretty basic, right? The only interesting part is my very simple class that tracks averages and standard deviations. I had to explain that I've never seen anyone do it before, but it's trivial. (Everyone should be doing it. They just don't for some reason; maybe statistics are scary.)

     The longest explanation was to the question: am I or am I not changing how fast the server runs by taking statistics in such extreme density? (I count everything: any time we have a new question, we get a new statistic.) The answer doesn't satisfy because it's an argument not backed by data. Maybe I'm eating as much as one percent of the cpu cycles. It depends on the mix. The scary part is wondering if I'm close to getting contention on the floating point unit. No way: the floating point math isn't that dense.

     (The stats don't occur inside highest latency code: touching lots of memory. They only occur at the end when I sample usecs of latency from the timestamp counter hardware register. So stats gathering necessarily happens a small percentage of instructions: it's only a bump on CPU use.)

     However, the cumulative average and standard deviation don't tell you how things are going lately; so if you want to know trends in recent time windows, you need to stack stats a little deeper, keeping a separate statistic for the last N samples, with a separate high seen during N. And because someone will ask, you need to show how many milliseconds passed during those N samples. (N is chosen for higher frequency than screen display of stats.)

     Of course, doing that's a pain in the ass, so I wrote it once in a C++ class named DiffStat rolling up all the crap in the last paragraph. Using it just instantiates an instance of another C++ class to drive it — all this evidencing a very irritating quality of C++: magic occurs as a result of constructing objects. Yes that part sucks, but it's better than coding over and over.

     So, you want to know the latency to lock one central mutex scaring the bejesus out of you? Measure it directly and put your mind at rest: evidence.

unit tests ¶

     Where I work I'm almost the only developer who writes unit tests for my code. It's not that tests are distasteful to most developers. They just have trouble thinking in a manner needed to generate indisputable evidence.

     Also, testing can be incredibly tedious: I took more than a work week to write a thorough multi-threaded monte carlo unit test for my page cache. But when done, the code worked correctly the first time I replaced VM memory mapping. (I was surprised it worked first time.)

     We try to follow an agile development process, so unit tests are encouraged as thematically fitting. One day we discussed whether there ought to be a standard interface. One of the guys who'd worked at Sun said: hey, the JUnit interface is cool and very popular.

     I said, um, I actually know something about that, but I don't like that way of testing much. These days when I test a class, I often add a static class method that looks like this one, to be called from main():

     And I seldom bother to use the parameters — they only have such names as a clue this test() method should be part of a standalone unit test, which returns zero on success and nonzero on failure. A failed test also prints a detailed diagnostic complaint. And a successful test prints a summary of how many subtests happily finished.

     In other words, I'm a total no frills guy.

test frameworks ¶

     Today Andrew Shebanow posted a piece on the history of test frameworks, prompted by reading about beautiful tests and origins of JUnit in Beautiful Code. Andrew saw JUnit's api looks like one I invented.

     JUnit really does look a lot like the api I did for unit tests at Taligent. In the image posted on Andrew's site, all JUnit method names are identical or nearly so to my original 1991 method names. When I first noticed this a while ago, I knew it copied my work. But I wasn't surprised to get no credit: that's how the world works. Credit goes to folks who follow through and beat drums. Andrew says:

The similarities seem fairly striking to me. Factor in the fact that Erich Gamma worked at Taligent at the time the Test Framework was developed, and in fact gave the engineering team some good feedback, and its pretty hard to argue that Alan and David don't deserve at least some credit for developing one of the original ancestors of JUnit.

     Yes, similarities are more than just striking: all the names match beyond coincidence. But the api wasn't very complex in the first place. I have trouble feeling slighted when there's little to my api. I struggled to invent more detail than setup, runtest, and cleanup hooks.

     Anyone would be forced to invent something similar since it's hard to give tests more structure besides adding tests to collections. Erich Gamma seemed a nice guy when I met him at Taligent: I don't want to beat him up, and don't think he deserves it.

     Here's my take on the matter: Alan and I should be credited with original design if someone must be. I don't feel burned without credit though. I guess I don't crave name recognition much. Andrew needs credit for the manual (I only wrote lots of code comments) and more credit for requesting the work.

     (I'd rather be credited for remote client/server scripting I did for automation. But there's no lineal descendent today unless you want to squint and count some stuff I'm doing lately — it's irrelevant here.)

     I think Alan Liu penned timing test subclasses and others in Taligent's framework. But I'm happy to share credit equally. Alan was a great engineer to work with, and I was tempted join him again a couple years ago. Alan deserves the credit: he gave more energy than me, and fleshed out the suite of classes. I was always try to escape association with tests.

      I also really enjoyed working for Andrew; I've often an urge to ask about a job: Adobe might be fun like jobs at Apple and Netscape. (You forgot to plug my OpenDoc years at Apple. :-) But I'm addicted to Linux servers now, and it's usually impossible to go home again, isn't it?

     Of all perks I enjoyed over the years, there's none I ever liked better in a job than working for someone clear headed and very intelligent, with instant comprehension. I hope your reports know they're lucky.

first person plural ¶

     I hate academic papers with one author using "we" instead of "I" to refer to the author. It always makes me think of movies parodying French kings. Maybe it includes cronies thanked in acknowledgments under a local social consensus umbrella.

naruto ¶

     Instead of starting to code first thing early today, I sat down for a couple hours watching part of a Naruto marathon with my two sons, who kept me informed with running commentary and catechism on abilities and attacks called jutsu.

     My younger son, who's twelve, fluidly mingled conversation with watching television and navigating through show websites on his laptop. It was like attending a seminar on Naruto, with analysis of fight tactics as thorough as a programming syntax.

     This was all fascinating because two weeks ago here I disparaged their knowledge of old popular culture (Robinson Crusoe), when all along their substitutes are more rich and detailed than mine, if anything. The show even offers lessons in abuse of power.

     I think I was most pleased by the way my younger son was actively involved by exploring websites, rather than passively eating lotus flowers. (Years ago I used to tell them a joke I once saw in a book, "The television loves you," when I wanted to tease them.)

     I stayed until I finally hit the joking stage. The show kept citing a fighter's forbidden secret jutsu (a bit much) so I invented forbidden bitchslap jutsu, reminding one son of the old joke comparing muscles needed to frown vs bitchslap I'd seen at work once.

ambiguous evidence ¶

     I've noticed Bruce Schneier tends to quote material with security implications I agree with from another perspective: most people are very bad at evaluating evidence, making them prone to interpret any and all data as confirming expectations.

     I think from a security view it means people can't see threats when most events look too "normal" to arouse suspicion when normality is expected. I've a more sociological view: failure to sync personal views is an expected result, not a surprise.

     Bruce Schneier quoted a piece from conspiracy theory with this paragraph emphasizing how ambiguous data can be readily used as support by folks holding diametrically opposed beliefs:

The study, which again involved giving volunteers fictional accounts of an assassination attempt, showed that conspiracy believers found new information to be more plausible if it was consistent with their beliefs. Moreover, believers considered that ambiguous or neutral information fitted better with the conspiracy explanation, while non-believers felt it fitted better with the non-conspiracy account. The same piece of evidence can be used by different people to support very different accounts of events.

     That's exactly in accord with my experience: most people let noise confirm any hypothesis. It's important since it means friends and family easily hold beliefs with zero support because random data looks like support when filtered by does-not-contradict testing.

     People around you can believe anything, and you can't infer any limits on what folks might hold true based on evidence you see, since they don't see data the way you do. (And any evaluation bolstering self worth gets strong positive bias.)

     Schneier thinks the piece helps explain current paranoia in the administration, since low probability random misfortune is elevated to big conspiracy when it paints a victim as worthy target of ongoing planned malice by competent arch enemies.

     Here I take no stance on public policy: it's only an observation on how evidence — or lack of it actually — gets interpreted under an agenda. But folks exist who think absence of stance is attack when only support is acceptable. Ambiguity is excluded middle.

over demand ¶

     My todo list got longer really fast this week, and I had to dance just to triage new demands. Usually my task queue is manageable. Now I have three higher priority things in front of my earlier tasks, and no time to do them with new stuff dropping in my lap.

     Anyway, I'm tired, and I've hardly had time to think about material I write about here. I should stop staying late at work training new folks, answering questions. I'm seeing a kind of mythical man month effect.

roadkill ¶

     A guy at work suggested a funny codename for a tool I started. I must show evidence my part of the system has only expected entropy. I need to compare shards of exploded pottery reformed in lossy vases. It's about as archeological as it sounds, sigh.

heresy ¶

     I enjoyed Freeman Dyson's piece on the need for heretics in science, as much for his praising usefulness of heretics as for nice writing. In technical matters, I find it hard to avoid being the heretic myself most of the time. So it's nice to see this role defended as inherently useful.

missing topics ¶

     You're missing two topics I successfully suppressed — I quelled an urge to discuss etags and gzip formats (neither related to one another). They're both interesting of course, but neither serves a useful purpose to me here. I'm shedding a daily impulse to write about all and sundry, hooray.

boot symbols ¶

     Today I added code to my virtual machine to instantiate well known symbols at "boot" time, with addresses stored in statically known member variables, so they can be checked at need during runtime. For example, the symbol for quote goes in a particular slot, so I can (eg) compare a symbol for equality to quote via pointer comparison.

     What's more, all symbols for special forms are allocated together contiguously to support an is-special-form? method that merely range checks addresses, so this can be done very fast when interpreting s-expression trees, without even first establishing whether an object is a symbol.

     These symbols, and other "globals" with expected permanent residence, live in a box heap structured for gc that will never actually be collected, so those symbols never move in memory, and address range checking stays valid. Below I discuss other properties of these symbols.

jump table ¶

     Because the s-expression interpreter will use a jump table (using switch in C) to dispatch special forms, I want consecutive integer values assigned to each special form symbol for efficiency, so a new enum does this. Then I just needed a fast symbol to enum mapping.

     A hashmap wasn't necessary because it turns out tags for my boxed gc memory format had plenty of unused bits reserved for later use: symbols had a fallow 7-bit field I could use to hold the special form enum value, so I did. Now special form symbols directly store a dispatch integer.

symbol format ¶

     My past interpreters had an easier symbol to enum mapping because all symbols were physically the same size, since their names were indirectly referenced, and I could use array position of special form symbols. But my current symbols are variable length, like strings.

     In fact, my symbols are a physical subtype of strings and can be used interchangeably with code taking immutable strings. (In fact, they're C strings in the sense they're nul terminated, and a pointer to a symbol box is a pointer to the first symbol octet. This is also the string format.)

     Symbols only differ from strings by what precedes the name in the gc heap. The four byte tag prefix marks the box as a symbol (and immutable). And each symbol instance is immediately preceded by a hash box with a crc32 hash. There's no link field for the interning hashmap.

typed continuations ¶

     When the þ VM later mixes native code, byte code, and s-expression code, the continuations will be distinguished by explicit typing, so each sort of code can call any other. Yes, it hampers speed slightly not to have total uniformity. But the flexibility enables interesting features.

     For example, you could experiment with new byte code schemes, since each scheme would be explicitly typed. Code migration of various sorts would be rather easy to test: e.g., JIT compiles from one byte code format to another.

enjoying work ¶

     I'm enjoying work in my day job a lot these days. But I get a surprising number of inquiries about jobs though. Why is that? The job market must be heating up. Please don't nag about work. Why would I want to release a perfectly good bird in the hand? Jobs good for me are few and far between.

network optimization ¶

     I'm not really a networking guy. Networking is just context for my work. I just hack user space code indirectly affecting how network traffic is done. I don't do network stacks or get far from application layers. It'd be more accurate to call me a caching guy. Give me space to encode stuff, and you get time optimizations and compression.

     I focus on runtime stuff like threads, memory, sync & async i/o, events, scheduling, frameworks, data structures, O(1) operations, locks, conditions, hashing, searching, indexing, matching, paging, statistics, etc. I massage data while riding the edge of space/time tradeoffs. A visitor recently winced and said it all sounded like rocket science.

     When I told a friend what I do last year, he said it was like signal processing: I don't change an end-to-end network signal — I just transform it temporarily in the middle for better bandwidth and latency. Sometimes my coworkers tease me about getting to do all the interesting stuff, since I revamp and grow the core engine of the server.

     I like doing it, so I count myself lucky. As far as I know, it's very uncommon to get an opportunity to rework and optimize basic i/o architecture in enterprise servers, and write a lot of code from scratch for the best results I know how to get. It's a plum assignment; I don't want to give it up. It's right up my alley, and has me solving problems I want solved.

     I get to play master plumber all day. To pay for it I need only field questions (often easy ones) on memory, threads, address spaces, mapping, alignment, testing, copying, contention, robustness, lifetimes, fragmentation, and things that can go wrong. I'm no one fancy or important: just one of the guys.

     The idea anything else might sound as interesting feels remote. Things that sound "challenging" (like startups) just seem troublesome — and I've experience with that. I've no taste for trouble, and money isn't an incentive when it comes coupled with argument, daily angst, and newly baptised coders certain they can do no wrong. I'm happy now.

long names ¶

     I did a search for Bell's first words over the telephone, and found a hit on this domain, whose name length was so funny I had to cite it here for laughs:

http://thelongestlistofthelongeststuffatthe longestdomainnameatlonglast.com/first30.html

short updates ¶

     I'm pretty sure soon I'll start writing minimal hundred word heartbeat updates every few days. I just got carried away today. It would be better if I kept it short, simple, and boring from now on, the better to convey nothing much is happening. (My progress seems okay, but I don't want to dwell on it.)

plan change ¶

     Here's my change in plan for this site: I'm going to downplay what I'm doing. There's a specific reason for this, which I'll explain if you bear with me. Most folks who describe what they're doing (for the benefit of others to hear) tend to over represent the value of whatever is involved.

     Generally speaking it's simply marketing. When you're in business, your goal is to get greatest demand for whatever you sell. Actual value plays second fiddle to demand — you only need as much value as required to keep up demand. Maybe this practice makes sense in a dog-eat-dog market.

     But I'm not in business. So I've been thinking: Why should I trouble myself to advertise what I'm doing if it has value? It's like putting out a "free food" sign and ringing a dinner bell for wolves. Why do that? Especially if I don't have resources to play games at all (even if I liked games).

unclean ¶

     These days I mostly say I'm creating a programming language, because they're (usually) free and intrinsically low in value as a manufactured good. In contrast, a few years ago, saying I was making a database invited trouble when folks valued that. So I emphasize tech sounding less tasty.

     Saying you're making another Lisp works quite well. (Ohmigod, not another Lisp, folks moan. :-) Even the most rabid opportunist never believes a killing can be made on a new Lisp, so you get peace of mind by falling right off the radar. I can't recommend it more. Stand back, I'm playing with a virulent language for outcasts.

java strings ¶

     (Let's refer to someone as Carson.) I was telling Carson about my approach to strings in þ since I think it'll have nice performance effects. Some of the main points to my approach include:

• delaying immutable status
• pointer and length representation
• scatter/gather format in large strings
• copy-on-write edits in big immutable strings

     (This isn't much different from my Mithril design years ago, but I might not republish much of that old spec.)

     Carson thought his past experiences in Java profiling showed much time lost in the implementation of strings due primarily to two interacting design errors. (I've used Java almost not at all, so I don't have my own opinion; thus I value what Carson has to say about this a lot.)

     Apparently the choice of 16-bit native unicode has unfortunate space costs, made worse by many allocations and reallocations of strings when editing immutable strings, so string processing in Java generates a lot of garbage and touches a lot of memory. (Touching memory is costly these days.)

     I told him my gc supports mutable state at first that can become immutable later when you're done making changes, and you know sharing with other threads can occur. It basically uses object granularity cooperative bitflags, enforced by the VM runtime. Imagine dynamically enforced const in C++.

     Carson thinks more efficient strings are a big win, and I agree. I've been working that angle a few years, since Netscape's 1999 era browser copied C strings promiscously in many layers. After Netscape, the next server I wrote used shared state pointer and length formats very effectively. I use them heavily still.

taligent objects ¶

     Carson was once a possible architect for PinkOS at Apple (which later became Taligent); I wish he'd become architect instead of [the actual architect], who was a big proponent of an extreme object philosophy that everything should be an object, leading to bad performance.

     When you try to force everything to be abstract at every level, comically stupid things happen to execution speed. In one Pink team communications meeting we saw an exhibit: a stack of printer paper listing every function call profiled between pressing a keyboard key and seeing a glyph appear on the screen after many thousands of method calls.

     This isn't smart on an 8 megahertz processor. (That's not a typo: 8MHz is much slower than today's 2GHz+ processors.) We had no control over distance between top and bottom: how far you must travel from highest APIs down to lowest basic primitives. This was one lesson I learned at Taligent: have your primitive layer in sight.

     Informed by this insight, it was around 1993 I first designed the prototype of all byte stream classes I've used since, with carefully and deliberately exposed primitive implementation detail as a primary optimization tactic, using polymorphic virtual methods only as a fallback mechanism. This amortizes costly abstraction over many extremely cheap inline calls.

cost metrics ¶

     Before I introduce basic, simple streaming classes, first note a measure of runtime cost I think about: function calls per byte. If your costs are directly related to text i/o in some encoding, one goal you might pursue is minimizing function calls byte byte of content processed.

     That should be obvious, right? And the lower this number gets — function calls per byte — the more important it is to cut more. (Saving one call in a zillion has little effect, but saving one of every two function calls has large effect.) For starters, you want cost to read or write one byte to be as small as you can get it: zero calls per byte on average.

     (I know, layers above the bottom streaming layer add cost, especially if you're going through unicode and i18n. But that doesn't mean you should give up and be slow everywhere. Play along with me here, and pretend speed of byte i/o matters. The same approach plays elsewhere.)

     This is easy to get, and basic technique looks very similar to what happens in typical implementations of getchar() in the standard C library, which is usually a macro — not a function. You can make an inline C++ method with even less cost if you avoid unnecessary arithmetic. As long as your buffer has room, you can do one more byte via pointer bumping.

primitive streams ¶

     Okay, this is a short overview of in and out streams using simple inlines for each byte read or written. (This is really old, but isn't very familiar to anyone I've shown before.) The key insight is this: streams are buffered, so expose buffer pointers for use in inline methods that work like macros.

     (An unbuffered stream also works, with almost no extra overhead. But you might as well throw in a small buffer for byte i/o, even if it's seldom used by bulk i/o. It's not like you're going to notice size cost of another 32 or 64 bytes.)

     For names let's use i and o for in and out, p and x for pointer and max, and 0 (zero) for origin. Every stream — in and out streams alike — represents a buffer using a system like this for 0, p, and x (with type prefixes):

     A base class for a yo outstream class aims to implement a putchar style method named oc() using these three standard buffer pointers:

     Note how little arithmetic occurs before *o_p++=c. When protected _oc() is called, a subclass flushes (o_p - o_0) bytes, then writes one more: param c. An unbuffered stream simply keeps nil in all three pointers, so _oc() is always called.

     Similarly base class for a yi instream class aims to implement a getchar style method named ic() using the three standard buffer pointers:

hermit crab ¶

     Beyond work and my sons half time, I've no social life — unless you count this site or other online presence as "social interaction." (I don't, except when speaking loosely.) I don't date, or visit with family, or hang out with friends, or network with programmers, or go places to see or be seen, or talk to anyone on the phone. I no longer play games. I've no significant other; I don't chat up women, or even speak to strangers. Socially, I'm a hermit. It once bothered me, but hasn't for a long time.

bad conversations ¶

     Many online conversations seem unpleasant and frustrating, primarily because other folks assume everyone else is ignorant of anything not yet loudly proclaimed. Polite behavior is read as cluelessness; brash or cocky behavior is read as knowledgable. So instead of asking questions, folks offer bad analysis, or advice based on cockeyed notions of what you mean or what you understand. Or they jockey to make others look bad, in a loosely defined king-of-the-hill game to upgrade their pecking order.

     I seem to learn little from online chats, except variations in how ideas affect egos, and in how persistently folks play counting coup in preference to exploring idea options. I've trouble seeing any redeeming value in threads I've joined in recent months. Is being lonely a good enough reason to let others beat you up? I'd say no. An educational beating is different; losing a game of chess teaches you to play better. (In chess I'm a good sport. I played many dozens of games of chess with one high school pal who always won. I didn't mind losing as long as I was getting better.)

     I don't think I'll participate on my favorite web site any longer. The ambiance of aggression is too ugly.

good conversations ¶

     I've been having great conversations at work with a guy who thinks similarly about many things. Great conversation is one of the big (but sadly rare) fringe benefits in work environments. Normally I don't have any coworkers who can talk with me about kinds of research I do on my own time. This is second guy in 18 years who adds intelligent commentary on any detail I care to mention.

     When I mentioned my OpenDoc work at Apple in passing, he asked whether our Apple tours had overlapped, and they had one year in 1995. Looking back, I suddenly remembered a meeting when we'd both been in the same room to review a third party database for Apple's use. Sometimes I still have photographic memory after ten years. I squinted and said, "Yeah, that guy looked just like you." And it was; I said he'd discussed long term transactions, and he nodded in confirmation.

generation gap ¶

     With today's top headline planned, I realized my two sons had probably never heard of Robinson Crusoe before, so I asked them point blank before writing tonight. They had me repeat myself several times, trying to pronounce what I said correctly. They hadn't a vaguest clue.

     Why had I suspected this, anyway? Why was I so certain they'd large gaps in their popular culture history? In recent months it'd simply become apparent, often just because they'd ask what certain basic English words meant when seldom often used in American television, or even Harry Potter books.

     They both read, but not nearly as much as I did when young. But I read more than 99% of other kids in my own generation. Beyond vast amounts of science fiction (trash, if you insist) I also browsed library stacks as a teenager and a college student. I read as much as normal teens hung out in malls — maybe more. My sons spend a lot of time playing video games. :-)

old fashioned ¶

     In the 70's I read a lot of science fiction written in the 40's, 50's, and 60's. Inadvertantly I steeped myself in the cultural mores of folks two generations my senior, and didn't realize I was doing this. My ideas of right and wrong — and the place of an individual in society — had more in common with World War II intellectuals than my own generation, which was just beginning the era of ultimate self indulgence and greed. (The current era is not very different.) I still haven't shaken my conviction the welfare of others comes first, and myself second.

     This old-fashioned view is so uncommon, it seems unlikely to others. And most folks rarely perceive what's actually there, in front of them. Instead, they sample evidence only to slot data in pre-conceived categories. So they see everyone else as self-centered, varying only in flavor, style, tactics, interests, etc. In fact, you think I'm lying, don't you? That would be simpler to believe: that I'm working a stale selfless angle in selfish pursuits.

     Of course, everyone with an altruistic streak, big or small, uses their own measuring stick when choosing what has priority. And this choice has a selfish quality, or merely very narrow perspective particular to one person's view. This makes even altruistic behavior look selfish: folks who are actually selfish view any thwarting of their wishes as selfishness in others. (Yes, it's infantile.)

     You suspect I'm preaching to you, so I can follow up by enjoining you to follow some new path of my own choosing, to further my own selfish ends. (Admit it, you thought that was one possible point of this line of discussion.) Actually, my point is really that nothing I say can make you think otherwise if your only model of others is self aggrandizing bots. I'm only making an observation: you see mostly what you want to see. You hoodwink yourself.

lisp advocacy ¶

     I like Lisp, or at least parts of Lisp, but I'm not advocating it much more than using and supporting it myself. You might easily expect I'll talk like other folks who use Lisp: like a fanatic. That's not gonna happen. I'm one of those moderate middle-of-the-road guys who say every tool has its purpose. I'm going to mix Lisp and C++ promiscuously. Is that bad? Wait it gets worse: I won't stop with mixing just two models.

     Some things you don't like about Lisp might be less a problem in my code, if I happen to use another tool more in some places. Like speed for instance. Suppose I interpret my Lisp a lot at first. How big an effect will this have? Well, doesn't that depend on the relative number of cycles spend in C++ and Lisp? I think it does. My C++ VM infrastructure might get big. If the bottleneck occurs in moving bytes around, that will happen in C++.

type safety ¶

     Sooner or later I'll add optional static type declarations to all the syntaxes I support. I like dynamic duck typing, but I also like enough static typing to save major headaches when I hack code down the road. I depend a lot on the minimal static typing C++ provides. I can often arrange my code runs more often the first time just through typing effort.

     But my typing support will be basic and lightweight: very little more than interface types. I added this kind of type safety to a language once before, in a professional work capacity, around 1994 when I added polymorphic dispatch to the runtime of a graphical dataflow language in my company's product. It wasn't hard, so I know it won't be hard a second time.

diminishing returns ¶

     You can see a very clear pattern to my taste in tech design: stressing more of any single tactic gets less and less priority, because diminishing returns renders each unit of extra energy expended on one strategy less effective. Using a new technique at all — some of the time — often has high initial value, even when not universal. But the more you pursue something, the more it costs and the less extra benefit you see.

     A mental metaphor I often use is a multidimensonal cube of tradeoffs, with every dimension axis corresponding to some feature or quality pursued more as you move away from the origin. Given resources you have to spend, some hypercube is a box bounding where you can reach in this space. The more you spend on one thing, less you have for others, and rate of cost increase goes up further from the origin.

     You can't maximize anything without blowing all your resources in one dimension. In contrast, initial spending on any dimension is cheap: you get far from the origin at low cost. The best first move is getting off the origin for all dimensions. Somewhere in the middle of the bounding cube is as far from the origin as you can get with limited resources. Your only cheap freedom of choice is favoritism, not dogged pursuit.

macro fans ¶

     I might've given the impression I like Lisp macros. Actually, I'm pretty indifferent. But supporting any new feature can yield good early bang for the buck. I just see no reason to pursue macros at length. Many Lisp advocates (I'm not one myself) cite macros in particular as a wonderful thing showing Lisp's excellence. It's minor to me.

     Around 2000 when I was leaving Netscape, I was interviewed by a great engineer with a Lisp background, and he asked what I thought of macros. I asked, did he mean C style text substitution macros? Or did he mean Lisp style list surgery macros? He said "Perfect!" — I knew the difference: good enough.

     Macros are another form of indirection, and all forms of indirection have similar effects: power from abstraction via substition, and obfuscation from varying options instead of being consistent. Strengths are often their own weaknesses, and vice versa. I'll harp on that meme a lot more soon.