Speedlink: Compilers.net

Compilers.net was recommended this morning on the Types mailing list as a good source for compiler frameworks. It has lists of compilers organized by language, a potentially handy resource.

Using Groovy to profile .class vs. getClass()

In Log4j template code in Eclipse, I mentioned two different ways of constructing a Logger instance:

Logger.getLogger(getClass());

and

Logger.getLogger(Foo.class);

and mentioned that the latter is supposed to be faster. Wondering how much faster led to an impulse to start creating a new Eclipse project and...

Then I thought "why write a new Java file? This is a perfect time to try Groovy." (If my goal was not to produce something persistent, I've failed because now we have this post.)

I recently installed Groovy, the dynamic scripting language with Java-like syntax and doubtful name, and fired up the Groovy console, a simple Swing application that functions as a kind of read-eval-print loop environment with one very useful feature, an object field and method explorer.

Bottom line: .class vs. getClass()

The bottom line is that accessing the static .class object was faster by about 20 times, at least in my tests using Java 1.4 in Windows:

Operation	Average time
getClass()	1281 ns
.class	62 ns
x++ for int x	1859 ns
loop overhead (not counted in other numbers)	78 ns

I would surely like to find some explanation for this gap. I'm sure all it would take is knowledge of how these two calls translate in the JVM, but that alas lies outside my knowledge.

Groovy code for profiling

I follow a standard pattern for profiling a block of code where you simply repeat the block some large number of times, sampling a timer before and after the loop, and then subtracting the loop overhead by timing the same looping construct with an empty body:

limit=1000*1000
import java.util.Date
t0 = new Date().time
for(i in 0..<limit)
{
 ;
}
t1 = new Date().time
loopoverhead = t1-t0
println "loopoverhead=${loopoverhead/limit} ms"

s = "foo"

t0 = new Date().time
for(i in 0..<limit)
{
 c = s.getClass()
}
t1 = new Date().time
tgetclass = (t1-t0)-loopoverhead
println "getClass()=${tgetclass/limit} ms"

The Groovy feature I liked here was the ability to write an expression inside the string literals. Also note the automatic getter translation of the phrase new Date().time, where the Java getTime() getter method call is available as a field reference time. One thing I wanted to do was to call System.currentTimeMillis() instead of constructing a Date object, but actually couldn't find in the docs how to invoke a static method.

---

Appendix: Groovy source code

limit=1000*1000
import java.util.Date
t0 = new Date().time
for(i in 0..<limit)
{
  ;
}
t1 = new Date().time
loopoverhead = t1-t0
println "loopoverhead=${loopoverhead/limit} ms"

acc=0
t0 = new Date().time
for(i in 0..<limit)
{
  acc++
}
t1 = new Date().time
intincr = t1-t0
println "integer increment=${intincr/limit} ms"

s = "foo"

t0 = new Date().time
for(i in 0..<limit)
{
  c = s.getClass()
}
t1 = new Date().time
tgetclass = (t1-t0)-loopoverhead
println "getClass()=${tgetclass/limit} ms"

t0 = new Date().time
for(i in 0..<limit)
{
  c = java.lang.String.class
}
t1 = new Date().time
tstaticclass = (t1-t0)-loopoverhead
println "String.class=${tstaticclass/limit} ms"

// Try with a non-system class

class Bob
{
}
testbob = new Bob()

t0 = new Date().time
for(i in 0..<limit)
{
  c = testbob.getClass()
}
t1 = new Date().time
tbobgetclass = (t1-t0)-loopoverhead
println "getClass() on non-system class=${tbobgetclass/limit} ms"

t0 = new Date().time
for(i in 0..<limit)
{
  c = Bob.class
}
t1 = new Date().time
tbobstaticclass = (t1-t0)-loopoverhead
println "Bob.class=${tbobstaticclass/limit} ms"

This Impredicative Sentence Talks about Itself

In which we learn a new word and check in on recent research in type inference.

Word of the day

William Safire's "Fumblerules" is a book on writing, a collection of short essays on various points of grammar and style, each based on a memorable self-explanatory example: "A writer must not shift your point of view" and "No sentence fragments." Fumblerules make the mistake they name.

While it's not a mistake, the title of this post is my self-explanatory example of our programming language word of the day:

impredicative

which is said of a definition that is self-referencing. Russell's Paradox uses a well-known example: "the set of sets that don't include themselves."

Self-reference and types

This word of the day comes to us via the paper "Boxy Types: Inference for Higher-Rank Types and Impredicativity" by Simon Peyton-Jones (with Microsoft Research in Cambridge, England) along with Stephanie Weirich, and Dimitrios Vytiniotis (University of Pennsylvania) from ICFP 2006, to my knowledge the only paper containing the phrase "plain as a pikestaff." (My money is on Peyton-Jones for contributing that one. ) But what were higher-rank types and impredicativity, I wanted to know.

A higher-rank type only makes sense with some background in parametric polymorphism, but I'll take a stab at explaining it. A polymorphic type is expressed with a universal quantifier "for all types a...", as in "for all types a, list of a -> int", the type of a polymorphic list length function. In general a polymorphic type can have any number of universal quantifiers. In Hindley-Milner, these universal quantifiers all come at the beginning of the type phrase. For any particular invocation of a polymorphic function, this means the polymorphic variables are each bound to one particular type. The higher-rank type means that the universal quantifiers can appear inside function types, allowing those polymorphic variables to be bound to different types within the body of the function. The utility of this is apparently in a kind of generic programming, as explained in Peyton-Jones work "Scrap Your Boilerplate", work done with Ralf Lämmel, another Microsoft Research employee.

The impredicative part of type inference is interesting. At first, I thought it meant recursive types, such as are used for linked lists. But I was puzzled how that could relate to this statement from the paper:

In the Hindley-Milner system, type variables range only over monotypes, but to allow function g we must allow a type variable—a, in the definition of Maybe—to be instantiated with a polytype. In the jargon, we need an impredicative type system, whereas Hindley-Milner is predicative.

After some digging, I think perhaps an impredicative type system is as the Wikipedia "Type polymorphism" indicates, one allowing impredicative polymorphism, allowing an instantiation of a variable in a type with the type itself.

The difference comes down to what is meant by "for all types" in the universal quantifier. In the predicative type system "for all types" is ranging over the monotypes, anything without a universal quantifier. More to the point, for all types does not include other polymorphic types... and therefore cannot include itself. In the impredicative type system, "for all types" can range over the polymorphic types too, and can include itself, hence the term "impredicative."

Call for input: Wikipedia article pointers?

Dear JFKBits readers,

I want your input. Are you interested in JFKBits including highlights of Wikipedia articles on topics related to programming languages, tools, and the mathematics behind it?

What I'm proposing is to add occasional posts highlighting an article, with a quoted excerpt and some discussion.

For several months now I have been consulting Wikipedia articles on related areas and found them very helpful. As in, man I wish this was around when I was going through grad school. For example, my view on closures came exclusively from the Essentials of Programming Languages by Friedman, Wand and Haynes. Now there's a concise explanation available on Wikipedia with examples for different languages and a wealth of useful external links.

To give you another example, right now I'm going back to some of my probability and machine learning course materials and trying some proofs. On the way, I'm running across the Wikipedia articles for

• Bayes theorem
• Bayesian inference
  
• Set theory
• Axiomatic set theory

and

• Mathematical constructivism

I didn't even know set theory was divided into "naive set theory" and "axiomatic set theory." There's a line in the section "Objections to Set Theory" that speaks of constructivism, which holds there is a loose connection between mathematics and computation. This is an idea, that computer science papers tend to be of a "constructivist" nature, that had been floated by me but I've never apprehended the full discussion or heard it fleshed out by practicing computer science researchers. Now I can peek behind the scenes and perhaps glimpse what that is all about.

So, I'm finding these articles helpful not only for the subject matter, but also for a view onto what's known, and what differing views and philosophies exist about the topics. Let me know if this is interesting for you, the JFKBits reader by leaving a comment.

One Logic Analyzer Per Child?

In checking out the Careers page of the One Laptop Per Child project out of curiosity, I noticed this opportunity:

Work with companies to develop a host of low cost peripherals for the XO laptop. Examples include the 10$ DVD player, a $100 projector, and a $0.10 oscilloscope adaptor.

Oscilloscope adapter?? Does anyone have any idea what this is about? "Here kid, we'll show you how to make sure you're little brother's PCI bus is clocking properly?"