Multi-cast delegates the evil way

A lot of people have asked me over the years how various kinds of event binding work.  Basically, event binding works like this:

1)     Someone clicks on a button,
2)     then a miracle happens, and…
3)     the button’s event handlers execute.

It’s that second step that people struggle with.

First, some terminology.  I studied applied mathematics, and somethings we talked about quite a bit were sources and sinks. Sources produce something — a faucet produces water at a certain rate, for example.  A sink takes that water away.  We’ll borrow this terminology for our discussion of events.  An event source is something that produces events, like a button or a timer.  An event sink is something that consumes events, like an event handler function.  (Event sinks are also sometimes called “listeners”, which mixes metaphors somewhat, but that’s hardly unusual in this profession.)

This terminology leads to a rather unfortunate homonymy — when I first heard “this method sinks the click event”, I heard “this method syncs the click event”.  When we talk about event sinks, we’re talking about the consumer of something, not about synchronizing two things in time.  (Sinks, of course, can be asynchronous…)

The miracle actually isn’t that miraculous.  Implementing event sources and sinks requires two things: first, a way to wrap up a function as an object, such that when the source wants to “fire” the event, all it does is invokes the sink’s wrapper.  Second, a way for the thread to detect that the button, or whatever, has been pressed and thereby know to trigger the sink wrappers.

An explanation of the magic behind the latter would take us fairly far afield.  Suffice to say that in IE, the details of how that mouse press gets translated into windows messages and how those messages are dispatched by the COM message loops behind the scenes are miracles that I don’t want to talk about in this article.  I’m more interested in those wrappers.

In the .NET world, an object that can be invoked to call a function is called a delegate.  In JScript Classic, all functions are first-class objects, so in a sense, all functions are delegates.  How does the source know that the developer wishes a particular delegate (ie, event sink) to be invoked when the event is sourced?

Well, in IE, it’s quite straightforward:

function doSomething() {  }
button1.onclick = doSomething;  // passes the function object, does not call the function

But here’s an interesting question — what if you want TWO things to happen when an event fires?  You can’t say

function doSomething() {  }
function doOtherThing() {  }
button1.onclick = doSomething;
button1.onclick = doOtherThing;

because that will just replace the old sink with the new one.  The DOM only supports “single-cast” delegates, not “multi-cast” delegates.  A given event can have no more than one handler in this model.

What to do then?  The obvious solution is to simply combine the two.

function doSomething() {  }
function doOtherThing() {  }
function doEverything() { doSomething(); doOtherThing(); }
button1.onclick = doEverything;

But what if you want to dynamically add new handlers at runtime?  I recently saw an inventive, clever, and incredibly horribly awful solution to this problem.  Some code has been changed to protect the guilty.

function addDelegate( delegate, statement) 
{
  var source = delegate.toString() ;
  var body = source.substring(
    source.indexOf('{')+1,   
    source.lastIndexOf('}'));
  return new Function(body + statement);
}

Now you can do something like this:

function dosomething() { /* whatever */ }
button1.onclick = dosomething;
// ... later ...
button1.onclick = addDelegate(button1.onclick, "doOtherThing();");

That will then decompile the current delegate, extract the source code, append the new source code, recompile a new delegate using “eval”, and assign the new delegate back.

OK, people, pop quiz.  You’ve been reading this blog for a while.  What’s wrong with this picture?  Put your ideas in comments and I’ll discuss them in my next entry.

This is a gross abuse of the language, particularly considering that this is so easy to solve in a much more elegant way.  The way to build multi-cast delegates out of single-cast delegates is to — surprise — build multi-cast delegates out of single cast delegates.  Not decompile the single-cast delegate, modify the source code in memory, and then recompile it!  There are lots of ways to do this.  Here’s one:

function blur1(){whatever}
function blur2(){whatever}

var onBlurMethods = new Array();

function onBlurMultiCast() {
for(var i in onBlurMethods)
onBlurMethods[i]();
}
blah.onBlur = onBlurMultiCast;
onBlurMethods.push(blur1);
onBlurMethods.push(blur2);

I’ll talk about VBScript and JScript .NET issues with event binding another time.

The JScript Type System Part Eight: The Last Blog Entry About Arrays, I Promise

Recall that I defined a type as consisting of two things: a set of values, and a rule for associating values outside of that set with values inside the set.  In JScript .NET, assigning a value outside of a type to a variable annotated with that type restriction does that coercion if possible

var s : String = 123; // Converts 123 to a String

Similarly, I already discussed what happens when you assign a JScript array to a hard-typed CLR array variable

var sysarr : int[] = [10, 20, 30]; // Create new int[3] and copy

and what happens when you assign a one-dimensional CLR array to a JScript array variable:

var jsarr : Array = sysarr; // Wrap sysarr

But what happens when you assign a hard-typed CLR array to a variable annotated with a different CLR array type?

var intarr : int[] = [10, 20, 30];
var strarr : String[] = intarr;

You might think that this does the string coercion on every element, but in fact this is simply not legal. Rather than creating a copy with every element coerced to the proper type, the compiler simply gives up and says that these are not type compatible. If you find yourself in this situation, then you will simply have to write the code to do the copy for you.  Something like this would work:

function copyarr(source : System.Array) : String[]
{
  var dest : String[] = new String[source.Length];
  for(var index : int in source)
    dest[index] = source.GetValue(index);
  return dest;
}

There are a few notable things about this example. First, notice that this copies a rank-one array of any element type to an array of strings. This is one of the times when it comes in handy to have the System.Array “any hard-typed array” type!

Second, notice that you can use the for-in loop with hard-typed CLR arrays. The for-in loop enumerates all the indices of an array rather than the contents of the array. Since CLR arrays are always indexed by integers the index can be annotated as an int. The loop above is effectively the same as

for (var index : int = 0 ; index < source.Length ; ++index)

but the for-in syntax is less verbose and possibly more clear.

Third, you might recall that GetValue (and SetValue) take an array of indices because the array might be multidimensional. But we’re not passing in an array here.  Fortunately, you can also pass only the index if it is a single-dimensional array.

Generally speaking, hard-typed array types are incompatible with each other. There is an exception to this rule, which I’ll discuss later when I talk about what exactly “subclassing” means in JScript .NET.

A grammatical aside

I just wrote in a comment to my previous entry, “The ability to rate one’s knowledge of a subject accurately is strongly correlated with one’s knowledge.”

Wait a minute.  “One’s”???  Word’s grammar checker didn’t blink at that.  But nor does it blink at “ones”.  According to the OED, “one’s” is the genitive declension of “one”.  Let’s sum up:

Pronoun   Genitive
-----------------
Me        My
You       Your
Us        Our
Him       His
Her       Hers
Them      Their
Thou      Thine
It        Its
One       One's

I always thought that the reason that “its” doesn’t take an apostrophe-s was because the rule “add an apostrophe-s to form a possessive” applied only to noun phrases, not to pronouns (And of course, we all know that apostrophe-s does not itself form a genitive noun — otherwise, in the sentence “The First Lady is the President of America’s wife,” Laura Bush would be associated with America, not President Bush.)

What the heck is going on here?  Surely there is some grammar pedant out there who can justify this.  My faith in English grammar has been sorely tried.


Update from 2023: My erstwhile colleague Mike Pope, who still writes an entertaining blog about English usage, gave some fascinating historical context.


Mike in 2003:

Well, let’s work backward.

In the phrase “The First Lady is the President of America’s wife”, the possessive is applied to the entire phrase: “(the President of America)’s wife.” This is common; here’s a nice example: “The woman I went to school with’s daughter”.

(http://www.chessworks.com/ling/papers/myths/mb003.htm)

FWIW, the ability to add a possessive to a noun phrase and not just to a noun is a comparatively recent development in English: “Until well into Middle English times what Jespersen calls the ‘group genitive’, i.e. ‘[the king of England]’s’ nose did not exist, but the usual type was ‘[the king]’s nose of England’. In Old English the usual structure, before the use of the of-possessive would have been ‘the king’s nose England’s’

http://www.linguistlist.org/issues/5/5-524.html

What’s actually interesting to contemplate is why the hell we have an apostrophe for the possessive at all. Possessive is just the genitive case; as such, it’s a normal noun declension, and has no more need for an apostrophe than the plural does. Nothing is elided with the possessive/genitive. And as noted, pronouns manage without it. German likewise has an -s for the genitive and manages without a possessive marvelously well. So whence the flingin-flangin possessive apostrophe, which does little more these days than confuse and annoy people?


Eric in 2023: I and other commenters pointed out that historically, possessives were formed by adding “es”, and the apostrophe indicates that the “e” has been removed, the same way an apostrophe indicates removal of letters in other contractions. “Its” was originally “ites”.


Mike again:

You’re on the right track with the “e” being elided with an apostrophe – that is indeed the origin of the use of an apostrophe as the indication of the genitive. What seems to have happened is that “ites” got elided, as frequently-used words tend to, but this happened much earlier in the history of English than the elision that happened to all other genitive forms. (Presumably because it was a widely-used word – the workhorses of a language are the ones that tend to get streamlined first, which is why the verb ‘to be’ is highly irregular in most languages.) So the progression looks like this: originally the word was “ites”, then it became “its” at a time when apostrophes were apparently not required on such elisions, and then quite a lot later, we started to elide *all* the genitive forms, but by then it was considered correct to indicate such elisions with an apostrophe.

[…]

The issue of elision of the vowel in genitive -es only partly explains the possessive apostrophe; the -as ending was also used for plural of masculine strong nouns in OE

(nice declension and conjugation chart here: http://www.engl.virginia.edu/OE/courses/handouts/magic.pdf),

which suggests that many noun plurals once had, as they did genitive singular, an unstressed vowel to go with their -s. Granted, it has less to do with how things really were than how they were perceived to be when our not-quite-rational system of orthography was being codified. As I sort of opined earlier, IMO the apostrophe is more trouble than it’s worth for possessives; even educated people are confused about its use, if my email Inbox is any evidence. In historical linguistics, mass confusion about forms is often a prelude to an evolutionary change. 🙂

Six out of ten ain’t bad

Occasionally I interview C++ developers. I’m always interested in how people rate themselves, so I’ll occasionally ask a candidate, “On a scale from one to ten, how do you rate your C++ skills?”

The point of the question is actually not so much to see how good a programmer the candidate is — I’m going to ask a bunch of coding questions to determine that. Rather, it’s sort of a trick question. What I’m actually looking for — what I’m looking for in almost every question I ask — is “how does the candidate handle a situation where there is insufficient information available to successfully solve a problem?” Because lemme tell ya, that’s what every single day is like here on the Visual Studio team: hard technical problems, insufficient data, deal with it!

The question has insufficient data to answer it because we have not established what “ten” is and what “one” is, or for that matter, whether the scale is linear or logarithmic. Does “ten” mean “in the 90th percentile” or “five standard deviations from the mean” or what? Is a “one” someone who knows nothing about C++? Who’s a ten?

Good candidates will clarify the question before they attempt to answer it. Bad candidates will say “oh, I’m a nine, for sure!” without saying whether they are comparing themselves against their “CS360: Algorithmic Design” classmates or Stanley Lippman.

I mention this for two reasons — first of all, my favourite question to ask the “I’m a nine out of ten” people actually came up in a real-life conversation today: OK, smartypants: what happens when a virtual base class destructor calls a virtual method overridden in the derived class? And how would you implement those semantics if you were designing the compiler? (Funny how that almost never comes up in conversation, and yet, as today proved, it actually is useful knowledge in real-world situations.)

The second reason is that ten-out-of-ten C++ guru Stanley Lippmann has started blogging. Getting C++ to work in the CLR environment was a major piece of design work, of a difficulty that makes porting JScript to JScript.NET look like a walk in the park on a summer day.

Compared to Stanley Lippmann, I give myself a six.


Update from 2023:

Two things:

First, a commenter on the original post mentioned an interviewing technique which I immediately adopted. When the candidate says “oh I’m an 8” or whatever, without calibrating the scale, the right follow-up question is: what is something that you found difficult when you were a 6 or 7? Make the candidate calibrate their own scale, and that’s then signal on how they should be able to handle the coding problems which follow.

Second, I was being somewhat tongue-in-cheek when I said that I’d follow up with a trivia question about the specification. Trivia questions are not great interview questions; as I noted in a comment to the original post, what I’m really looking for is not whether the candidate can regurgitate the specification on command, but rather whether they know that compilers are not magical; compilers need to generate code which implements the specification, and there are common techniques for doing so; do you know what they are? It’s all about gaining signal on how productive the candidate could be when solving problems we will actually face on the job.

Speeding can slow you down

I’ve been meaning to talk a bit about some of the performance issues you run into when tuning massively multi-threaded applications, like the ASP engine.  I’d like to start off by saying that I am by no means an expert in this field, but I have picked up a thing or two from the real experts on the ASP perf team over the years.

One of the most intriguing things about tuning multi-threaded applications is that making the code faster can slow it down. How is that possible? It certainly seems counter-intuitive, doesn’t it?

Let me give you an analogy.

Suppose you have an unusual road system in your town.  You have a square grid of roads with stoplights at the intersections. But unlike the real world, these are perfect traffic lights — they are only red if there actually is another car in the intersection. Unlike a normal road, each road goes only one way, and has at most one car on it at a time.  Once a car reaches the end of the road, it disappears and a new car may appear at the start. Furthermore, there is a small number of drivers — typically one or two, but maybe eight or sixteen, but probably not one for every car. The drivers drive a car for a while, then stop it and run to the next car!  The drivers are pretty smart — if their car is stopped at a red stoplight then they’ll run to a stopped car that is not at a red stoplight (if one exists) and drive it for a while.

In our analogy each road represents a thread and each stoplight represents a mutex.  A mutex is a “mutually exclusive” section of code, also known as a “critical section”.  Only one thread can be executing in that code at one time. The car represents the position of the instruction counter in this thread.  When the car reaches the end of the road, the task is finished — the page is served. The drivers represent the processors, which give attention to one thread at a time and then context switch to another thread.  The time spent running from car to car is the time required to perform a thread context switch.

Now imagine that you want to maximize the throughput of this system — the total number of cars that reach the end of their road per hour.  How do you do it?  There are some “obvious” ways to do so:

  • hire more drivers (use more processors)
  • eliminate some stoplights by building overpasses at intersections (eliminate critical sections)
  • buy faster cars (use faster processors)
  • make the roads shorter (create pages that require less code)

You’ll note that each of these is either expensive or difficult.  Perf isn’t easy!

Now, I said that these are “obvious” ways to solve this problem, and those scare quotes were intentional.  Imagine a complex grid of roads with lots of stoplights, a moderate number of cars on the road, and two drivers.  It is quite unlikely that cars will spend a lot of time stopped at stoplights — mostly they’ll just breeze right on through.  But what happens when you throw another six drivers into the mix? Sure, more cars are being driven at any one time, but that means that the likelihood of congestion at stoplights just went up. Even though there are four times as many drivers, the additional time spent at stoplights means that the perf improvement is less than a factor of four. We say that such systems are not scalable.

Or consider a moderately congested freeway system with a whole lot of cars, drivers and intersections.  Now suppose that you keep the cars, drivers and intersections the same, but you shrink the whole system down to half its previous size. You make all the roads shorter, so that instead of having eight stoplights to the mile, now you’ve got twenty. Does total throughput get better or worse?  In a real traffic system, that would probably make things worse, and it can in web servers as well.  The cars spend all their time at intersections waiting for a driver to run over to them. Making code faster sometimes makes performance worse because thread congestion and context switches could be the problem, not total path length.

Similarly, making the cars faster often doesn’t help. In the real world of Seattle traffic, upgrading from my 140-or-so horsepower Miata to a 300 HP BMW isn’t going to get me home any faster.  Getting a faster processor and shorter program only helps if the “freeway” is clear of traffic. Otherwise, you sit there in your souped-up ultimate driving machine going zero at stoplights like everyone else.  Raw power does not scale in a world with lots of critical sections.

When perf tuning servers, use the performance monitor to keep a careful eye on not just pages served per second, but on thread switches per second, processor utilization and so on.  If you cannot saturate the processor and the number of thread switches is extremely high, then what is likely happening is that the drivers are spending way too much time running from car to car and not enough time actually driving. Clearly that’s not good for perf.  Tracking down and eliminating critical sections is often the key to improving perf in these scenarios.