Archive for July, 2004

Fun with bits

When I interview someone, I usually ask at least one bit-shifting question to
the candidate.  It’s not a dealbreaker if she fails to answer it, but it
certainly wins her a lot of points if she can, or at least discuss
it in convincing ways.

Interestingly, pretty much every single candidate that I have ever
interviewed who did well on the other questions that I asked (typically at a
higher-level, such as OO design or design pattern) also does well on the
bit-shifting question, so it’s usually a pretty strong indicator of someone who
has a good computer science background overall.

There are three categories of bit-shifting questions that I usually pick
from, in increasing order of difficulty:

  1. How can you determine if a number is a power of two?
  2. How can you clear the rightmost bit?
  3. How can you count the number of 1 bits?

This last question is a classic, so I added my own personal twist to it (see
below).

Let’s take them in turn.

1.  How can you determine if a number is a power of two?

The easiest way to answer this question is to notice that a power of two
has exactly one 1 followed by only zero’s (except for 1, which is also covered by the following
solution).  Therefore, the quickest way is probably:

return x != 0 && (x & (x-1)) == 0;

The idea is that subtracting one from such a number will flip all its bits: 
the 1 becomes a 0 and all the zeros become 1.  "and"ing these two numbers
will therefore equal to zero.

As far as I can tell, this only happens for powers of two:  if the
number has any other 1 than the one we are interested in, it will not be flipped
by the subtraction and will therefore survive the &.

I will accept any variations thereof:  at this point, I am just trying to see
if the candidate has any notion of binary coding.

2.  How can you clear the rightmost bit?

There are several ways to answer this question and ideally, the candidate
will start by giving me the easiest one and then, the bit-oriented one when
pressed.  You can simply observe that clearing the rightmost bit is a no-op
is the number is even and a decrement of the number if it is odd:

return (n % 2 == 0 ? n : (n - 1))

This is not very efficient so I will ask for a faster solutions.  There are
a couple of options:

return n - (n & 1)

or

(n >> 1) << 1

This last solution is mine, and I prefer it over the others because shifting
is much faster than subtracting.  If the candidate doesn’t provide it, I
will usually suggest it and ask her to discuss the pros and cons of each.

3. How can you count the number of 1 bits?

And finally, we reach this timeless classic.  If the candidate
has never heard of it, she’s in for a tough time.  And even if she does, I
have my own twist to it that guarantees me that I will get to take a close look
at the way she thinks.

Let’s start with the naive solution:  shift the number right and
increment a counter each time the rightmost bit is 1:

int counter = 0;
while (n > 0) {
if (n % 2 == 1) counter++;
n >>= 1;
}

Next comes the leap of faith:  "This algorithm executes p times, where p is
the size in bits of n.  Can you think of a solution that executes in b
times, where b is the number of 1 bits in n?".

Either she knows the answer or
she doesn’t, and if she doesn’t, she’ll be stumped.  At this point, I will
step in and I will give her a hint:  "Can you describe to me what the
expression n & (n-1) does to n?".

If you’ve never seen this trick, it’s impossible to answer right away: 
you will need to apply the formula on the board on a few numbers before you put
the pieces together (which is already not very easy).  The answer is: 
"It clears the rightmost 1 bit in n".

With this in mind, the solution to the puzzle becomes:

int counter = 0;
while (n != 0) {
counter++;
n = n & (n-1);
}

If she gave me this answer without help, I will strongly suspect that she
already knew the trick, so I will throw in my own twist:  "Can you
demonstrate that n & (n-1) clears the rightmost bit?".

And I will leave
this as an exercise to the reader for now.  Answer in a few days.

 

Configuration injection in tests

Why does JUnit force you to have test() and setUp() methods that don’t have any
parameters?

Because there is no easy way in Java 1.4 and under to specify the values for
these parameters.

As a consequence to this shortcoming, various JUnit add-ons have added the
possibility to look up property files in your setUp() method which are then
initialized inside your test method (and incidentally, will be initialized over
and over again for each invocation of the test method, as I reported in an
earlier JUnit bug report).

A better way to address this problem is to use annotations as a bridge
between your Java code and a property file.  I just added support for this
in TestNG, and here is how it works (excerpt from the new TestNG documentation).

Parameters

Test methods don’t have to be parameterless.  You can use an arbitrary
number of parameters on each of your test method, and you instruct TestNG to
pass you the correct parameters with the parameters method on the @Test
annotation.  For example:

@Test(parameters = { "first-name" })
public void testSingleString(String firstName) {
System.out.println("Invoked testString " + firstName);
assert "Cedric".equals(firstName);
}

In this code, we specify that the Java parameter "firstName" of your Java method
should receive the value of the property called first-name.  This
property is defined in the testng.properties that you used to invoke this test:

#testng.properties
first-name = Cedric

The same technique can be used for the
@Configuration annotations:

@Configuration(beforeTestMethod = true,
parameters = {"datasource", "jdbc-driver")
public void beforeTest(String ds, String jdbcDriver) {
m_dataSource = ...;  // look up the value of datasource
}

This time, the two Java parameter ds
and driver will receive the value given to the properties datasource
and jdbc-driver respectively.  Note that the properties are mapped to the
Java parameters in the same order as they are found in the annotation, and TestNG will
issue an error if the numbers don’t match.

This system allows for a flexible configuration of the runtime configuration of your
tests and allow you to arbitrarily define how granular this configuration will
be (configuration method or test method).

Anonymous nonsense

What is up with this insistence of certain bloggers to require non-anonymous
commenters?

I was once again reminded of this curious obsession while reading Geert’s
comment on his own blog:

No, I delete posts from "No one" <noone@email.com>. If you can’t be troubled
to at least make yourself look human, I can’t be troubled to give you an answer.

but he’s certainly not the only offender.

It’s very simple:  either you allow people to post with a default (e.g.
noone@email.com) email address, or you just don’t
let them post in the first place.  Letting them post and then deleting
their post just because they didn’t feel the need to type a bogus email address
is just plain ridiculous, and a waste of time both for you and for the poster. 
Especially if you didn’t even bother spelling out the rules you follow to decide
whether a comment is worthy of your blog or not.

I actually even question the attitude in the first place.  Tell people that
they need to submit a real name and not an anonymous one and they will either
stop posting comments on your blog or sign them John Smith.  And what have
you gained, really?

Stop judging people on their identities to avoid addressing what they write. 
This is the Internet.  Deal with it.

Update:  the original poster addressed this very point by posting his
next comment under Geert’s own identity.  I rest my case :-)

Overriding annotations

While annotations have been very well received by the community, I have
repeatedly been asked at JavaOne about the possibility of overriding certain
annotations later during the cycle (at deployment time).

Here are a few
thoughts on this subject.
 
The overriding is specified in an external XML file which could look like this:

<override>
  <annotation-class names="javax.ejb3.TransactionAttribute" />
  <scope>
    <package names="com.foo" />
    <class names="Account" />
    <method names="deposit withdraw" />
  </scope>
  <overridden-values>
    <value name="value"
           old-value="javax.ejb3.TransactionAttributeType.SUPPORTS" />
           new-value="javax.ejb3.TransactionAttributeType.REQUIRED" />
  </overridden-values>
</override>

An override is specified with three parameters:

  1. What annotation type is being overridden .
  2. Hani pointed out that he didn’t like space-separated names, which I tend
    to agree with.
  3. The syntax should allow for regular expressions, including the
    possibility to exclude certain patterns.
  4. The scope of the override (which Java elements are impacted:  package, class,
    method, field, etc…).
  5. Which values are overridden and what the new values are.

Notice in the file above that "names" is plural, so you can specify several
space-separated elements each time.
 
Anything under a scope is "and’ed" together.  In the example above, only methods
named "deposit()" and "withdraw()" inside the class com.foo.Account will be
candidates for overriding.  We could imagine having several <scope> stanzas to
specify that an "or" should be used instead.
 
The <overridden-values> stanza specifies the new values that need to be applied
to the Java elements targetted by the <scope> stanza.  The first part must be a
valid name of the annotation type (TransactionAttribute.value() in this
example).  Optionally, you can specify an old-value in order to further restrict
the scope of the overriding.  In the above example, overriding will only apply
if the targetted element has a current transaction attribute "SUPPORTS".  If it
doesn’t, the override will not happen.
 
The matching of the values in the XML file to the actual enum type can be
performed through reflection, including enums, since it is possible to retrieve
a String version of each enum value.
 
The API could probably be very similar to the existing one:

AnnotationOverrider ao = new AnnotationOverrider("override.xml");
Method m = ...;  // retrieve the method
TransactionType oa = ao.getAnnotation(m, TransactionType.class);
// oa.value() now contains the overridden annotation

Here are some open questions/concerns that have come up so far:

  • We should be able to override defaults as well.
     
  • Should we make it possible to insert annotations and not just override
    existing ones?
     
  • Specifying compound values could be problematic.
     
  • Is the syntax too verbose?  For example, Bill Burke is suggesting
    to insert entire Java snippets to identify the targets:

    <annotation method="public void setEM(javax.ejb.EntityManager)">
    @javax.ejb.Inject
    </annotation>

    I personally think that writing Java code in an XML file is a very
    strong design smell, and it’s a step backward since we are reintroducing
    redundancy in the programming model (if you rename this method in your
    Java code, you need to remember to update the fragile string in your
    deployment descriptor).

Please let us know what you think.

The old goto problem

I was once again reminded of the constant controversy that surrounds the use of
goto by the two following posts:

I enjoy reading Raymond’s blog immensely.  Raymond is a consummate
Windows programmer and his blog contains a wealth of tips and tricks and
explanations of the Windows API that will make you see things in different ways. 

This particular entry involves a long snippet of COM code that is, frankly
speaking, quite scary.  Raymond made a point in this entry of not using any
external library (such as ATL, which cuts down the number of COM coding needed
for this kind of trick) in order to show exactly what is happening behind the
scenes.  This is a laudable intent but I couldn’t resist adding the
following comment on his blog:

I believe the only point you’ve made is that only VB or C# should ever be
used to access COM :-)

Raymond also made a point of not using goto in his code snippet and COM being what
it is, you need to constantly check for return codes and branch your code
appropriately, which results in the frightening code you can see in his column.

In the same spirit, Rich wonders if his coding style is not obsolete. 
He observes that the various seminal papers and books, such as "goto considered
harmful
" and "The elements of programming style", are over ten years old and
wonders if they are still relevant.

I can only salute Rich’s willingness to question his habits.  Very few
programmers ever do that and once they have settled in a comfortable programming style and
set of tools, they hardly ever move away from it.  It is a very healthy
attitude that I strongly encourage around me.  And in case you are wondering, an easy
way to see if you are flexible is to stop using your current source editor and
try another one (i.e. try an IDE if you are using emacs or try Eclipse if you
are using IDEA).

Back to the goto problem, I believe Raymond’s code is the perfect
illustration of the few cases where goto actually improves the readability of
your code, and somebody was quick to point that out in the comments. 
Cascading error cases is a good illustration of the power of goto’s, but you
need to remember that languages that support exceptions are slowly making this
kind of programming obsolete.  There is no excuse to use return codes to
signal errors in Java, C++ or C#.

In the meantime, use goto sparingly and make sure you explain why you do so
in a comment.

Announcing Doclipse 0.6.0

I just released Doclipse 0.6.0, which contains a lot of improvements over the
previous version:

  • Fixed: revamped the preference screen
  • Added: options to control spaces and double quotes
  • Fixed: better parser
  • Fixed: multiple targets were broken
  • Added: OJB mapping file (thanks to Thomas Dudziak!)
  • Fixed: couldn’t put an XML comment at the top of the definition file
  • Added: lazy loading of XML parsing
  • Added: many more definition files (thanks to Craig Walls!)

Check out the new documentation, I
updated it and it contains screenshots of the new preference pages (I broke them
down in several pages now).

Document-splitting: the solution

In case you didn’t read the comments on my previous weblog entry:  Jeff
Mesnil wrote two quick yet very ingenious bookmarklets that allow you to split a
Web page horizontally and vertically.  The bookmarklets can be found

here
and you can read some additional thoughts on the probleme

here

Thanks, Jeff!

 

Document-splitting in Web browsers

It’s not very easy to innovate in the Web browser business.  Except for
tab browsing and pop-up blocking, we haven’t seen a lot of innovations these
past years (and certainly not from IE, which has been stagnant for more than
five years now, although there seems to be some change on the horizon). 

Netscape/Mozilla/Firefox can certainly be commended for trying to innovate
constantly, but it’s quite interesting to see that even their valiant efforts
haven’t yielded a web-browsing experience that is radically different from the
way we were surfing five years ago.  I started thinking about this and I
couldn’t come up with any big hole in usability or functionality that I would
really like to see in my Web browser.

Except for…  document splitting.

This is a feature that has been present in Microsoft software for years now,
and it allows you to split the current document in two different parts that can
be scrolled independently.  This is a very useful feature for all kinds of
documents :  Word, spreadsheets, even Java source files (still waiting on
this feature to make it into Eclipse), etc…

And of course, Web browsers.

Just recently, I was reading an article that showed a figure at the top and
which constantly referred to this figure in the rest of the article.  Right
now, the only thing I can do is:  open a new window, paste the current URL,
move that window side-by-side with my current document and resume reading in the
original window.

All of this would be so much easier if I could split the original document
horizontally or vertically with just one click and drag…

Does anyone know of such an extension for FireFox, or should I file an RFE?

 

No-op methods

I have been exchanging emails with Patrick Linskey recently about
the thread on
TheServerSide.com
discussing callback interfaces for EJB 3.0.  Patrick sides
with the proponents of "one method per interface" but he is the first one to
produce a convincing argument:

So if you have lots of business logic in your jdoPreDelete() callback
(validating that the delete is allowed, deleting related external
resources, etc.), and you do a bulk delete and *don’t* bring the
objects into the VM in order to execute the callback, then some of the
intended consequences of a delete may not be performed.

In short, Patrick is saying that it can be important for the container to
determine if the callback it is about to invoke is a no-op or if it contains an
implementation written by the user, because the container might have some
potentially expensive work to do before invoking the said callback.

If each callback is encapsulated in its own interface, making this decision becomes
a simple matter of testing instanceof on the object:

if (o instanceof ILoadCallback) {
  ((ILoadCallback) o).onLoad();
}

The assumption here being:  if the developer declared she implements
this interface, she is going to provide an implementation for the method it
contains, so it should always be called by the container.  Therefore, there are
indeed cases when you need to know whether the method you are
going to invoke is empty or not.

But are interfaces the best way to solve this problem?

The more I thought about it, the more this problem reminded me of marker
interfaces (Serializable, Cloneable), which solve a real problem by pushing the
usage of interfaces beyond what it was designed for.

Then it occurred to me that annotations would probably a better way to do
this.  For example, we could create a simple @NoOp annotation:

import java.lang.annotation.*;
@Retention(RetentionPolicy.RUNTIME)
@Target(java.lang.annotation.ElementType.METHOD)
public @interface NoOp {
}

All the classes that implement the callback methods with empty
implementations can be flagged with the @NoOp annotation:

public class LoadCallbackAdapter implements ILoadCallback {
  @NoOp
  public void onLoad() {}
}

And any class that extends this adapter will simply override the method
without the annotation:

public class MyClass extends LoadCallbackAdapter {
  public void onLoad() { /* ... */}
}

The nice thing about this technique is that it is totally transparent to the
user:  they don’t need to know about the @NoOp annotation at all.  But
the container will be looking for it, and if it can’t find it, it will invoke
the callback:

Method m = o.getClass().getMethod("onLoad", null);
if (null != m.getAnnotation(NoOp.class)) {
  // invoke o.onLoad()
}

Personally, I find this approach cleaner than using interfaces, which
pollutes the type system of your object to address a concern that you should
know nothing about.

Why GridBagLayout must die

If you have ever tried to understand how the GridBagLayout works, I am sure
this will
strike a chord.