July 26, 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:
- How can you determine if a number is a power of two?
- How can you clear the rightmost bit?
- 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.
July 24, 2004
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).
July 23, 2004
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 :-)
July 22, 2004
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:
- What annotation type is being overridden .
- Hani pointed out that he didn't like space-separated names, which I tend to agree with.
- The syntax should allow for regular expressions, including the possibility to exclude certain patterns.
- The scope of the override (which Java elements are impacted: package, class, method, field, etc...).
- 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).
July 21, 2004
The old goto problem
I was once again reminded of the constant controversy that surrounds the use of goto by the two following posts:
- Raymond Chen's article on a COM trick to track the Explorer folder.
- Rich Burridge's thoughts on current programming style.
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.
July 19, 2004
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).
July 18, 2004
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!
July 16, 2004
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?
July 15, 2004
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.
July 13, 2004
Why GridBagLayout must die
If you have ever tried to understand how the GridBagLayout works, I am sure this will strike a chord.
July 12, 2004
The ultimate weapon against spam?
This article describes a simple system that has good chances to become a very effective protection against spam.
Comments welcome (except for the Slashdot spam form).
July 11, 2004
The poor shape of Unit Testing
Greg explains why he likes JUnit:
there are two things that make JUnit great:I certainly acknowledge point 2 since I provide a JUnit mode in TestNG (read: I emulate JUnit's bugs :-)). But you can't possibly be serious about point 1, Greg, can you? What is good about JUnit is what they left out?!?
- what they left out and
- the fact that it's pretty much THE standard for writing unit tests
Here is what happens when a framework is not only simple but simplistic: people start fixing its deficiencies on their own and you end up with an explosion of customized tools built on top of it.
Witness the following email, that was posted on the Groovy mailing-list just yesterday where Guillaume Laforge explains what they have added to JUnit to make testing easier:
Moreover, there are some other convenient assert* methods:
- assertArrayEquals(Object[] expected, Object[] value)
- assertLength(int length, char[] array)
- assertLength(int length, int[] array)
- assertLength(int length, Object[] array)
- assertContains(char expected, char[] array)
- assertContains(int expected, int[] array)
- assertToString(Object value, String expected)
...
(by the way, the Groovy dudes have added some pretty cool JUnit stuff to their shell, you should check it out)
Greg adds:
I for one am glad not to have to deal with multiple frameworks.
That's an interesting thought too. I tend to favor the other approach, though: encourage people to be creative and come up with all sorts of crazy ideas and frameworks, and let the market pick a winner. I mean... are you really saying you wish there was Struts and only Struts?
Every new project you start on you'd be learning yet another testing framework.
No, you are mixing up "concepts" and "implementations". The concepts of unit testing are fairly basic and well-known, and even though TestNG and JUnit offer two radically different approaches to this problem, they implement the same idea and I'm pretty sure that a developer familiar with one will have no problem switching to the other.
At any rate, my goal was to get people to rethink unit testing and question what they consider for granted, so at least, TestNG was successful in that. Finally, be sure to read Mike's recent blog entry, where he summarizes the main issues with unit testing quite eloquently.
July 09, 2004
Templates in Visual Basic
For those of you still complaining about the introduction of Generics in Java, know that Visual Basic will have Generics as well in Whidbey (the next version of Visual Studio):
Class MyCollection(Of ElementType)
Sub Add(Byval key As String, Byval Element As ElementType)
'Note that the type parameter ElementType is being used inside
'the generic type just like any other type
'
Dim Element2 As ElementType
...
End Sub
...
End Class
Dim IntegerCol As New MyCollection(Of Integer)
Dim DateCol As New MyCollection(Of Date)
Needless to say this beast bears very little resemblance with the Basic of my childhood (Applesoft Basic).
July 08, 2004
TestNG precisions
Robert (sorry, couldn't figure out his name) wrote a few interesting criticisms about TestNG:
JUnit's got huge traction in the Java community because of the tool support.
I disagree. I think JUnit got traction because there was nothing else when it came out. It was simple, lightweight, easy to use, so everybody adopted it. Fair enough. Then its limitations started showing and since its development was pretty much stopped then, people started building tools to work around its limitations.
And here is where I think the problem is with JUnit: the JUnit tools fix deficiciencies in its design. For example, the ant task allows you to launch the runner on a wildcard of classes or suites, which you can't do with JUnit. A lot of the value added by these tools should have been retrofitted in JUnit by now. But they haven't, because JUnit is basically a dead project by now.
If the only way you can easily launch tests remains from the command-line, it's not going to work very well.
I am not so sure about that either. Running tests from your IDE is definitely a plus (and I plan on writing an Eclipse plug-in once Eclipse understands JSR 175 annotations), but I believe that most of unit testing happens in automated builds. A good testing framework needs to be extremely flexible from the command line, that's a requirement. Which, as I said above and in previous postings, JUnit fails to achieve in many ways.
Case in point: how can I easily launch, in TestNG, both my older JUnit tests and the new-fangled ones?
It's pretty easy to do, but you will need to run the launcher twice. This is just because I made the "JUnit compatibility flag" per-suite instead of per-test. It seems to make more sense this way, but this is pretty easy to modify.
I hate the way the only log format for TestNG is a HTML file.
I agree. This was just a proof of concept to get you started. Right out of the box, TestNG gives you an easy-to-read HTML page that the most novice user can read and understand. But TestNG is fairly extensible and easy to modify. Since it's such an early stage, I haven't had the time to polish that part yet, but there is an important part of TestNG that you might have overlooked: it gives you an API to inspect its running process.
For example, you can add listeners that will keep you informed when a test starts, when it ends, if it succeeded, if it failed, why, etc... As you can see, adding your own logger and report generator is straightforward. In comparison, JUnit is a big black box.
There's not a single Decorator in sight in TestNG.
Let's take this offline, I'm not quite sure what you are asking for here.
Not to be nitpicky, but... I absolutely loathe the use of the 'I' to mark an interface. Can't stand it. Makes me shudder and have flashbacks to when I used to write Microsoft COM code in C.
Ah, well, sorry about that. It's a widely-used standard, though (Microsoft, Eclipse and WebLogic Workshop use it, and they certainly know their stuff...). You'll get used to it :-)
At any rate, thanks for the feedback. Contrary to what a lot of people think, I didn't write TestNG to kill JUnit but to make people think. So many toolkits and frameworks are considered for granted these days that nobody even thinks of improving them any more (e.g JUnit, Velocity or XDoclet to name a few). If TestNG causes JUnit to be improved, I'm all for it!
That being said, I have had a few more ideas to improve TestNG recently, which will show how powerful annotations can be compared to the "old way". Stay tuned, I'll blog about this very soon.
Robert, feel free to email me so we can continue the discussion!
July 05, 2004
AOP panel at JavaOne
The AOP panel at JavaOne was a big success. Maybe it was because of the provocative title ("AOP : The next big thing or giant leap backward"), which was concocted by the mischievous Graham. Maybe it was because James draws a lot of attendance. Or maybe, just maybe, it's that more and more people are getting extremely curious about AOP.
The panel was moderated by Simon Phipps and featured:
- Gregor Kiczales, as the "father of AOP".
- Graham Hamilton, as "the skeptic".
- Myself, as the "Conflicted AOP advocate"
- James Gosling, as... well, himself.
Somebody told me after the panel that not only was the main room full, but the overflow room was standing room only, which probably adds up to an audience of 2000-2500 people.
Simon opened the debate by asking a quick show of hands asking how many people had already heard of AOP, and I estimate that 90% of the hands came up. When the question was refined to "Who has used AOP?", a great deal of hands went down but quite a few remained up.
Gregor opened the debate by a ten-minute introduction on AOP, which is quite a tour de force. Using a simple application drawing shapes, Gregor quickly showed how concerns get scattered into your code, what aspects and pointcuts are and how they can help you write cleaner code.
Graham raised concerns about the loss of simplicity seen in the approach offered by AOP. He said that throughout the years, Sun has gone to great lengths to keep the language simple, but with AOP, a simple Java line such as "a = b * foo()" no longer means what you think it means.
When my turn came, I explained the reason for my internal conflict. In short, I see a lot of potential in AOP but I still perceive it as extremely complicated and representing a steeper learning curve than most Java developers are willing to climb. I will expand on these ideas in a separate blog entry.
Finally, James offered his ideas on AOP, starting by his very simple opening: "I like AOP a lot". His concerns are a bit different from Graham's, though: James is more afraid of the paradigm shift represented by AOP while we are just barely getting used to OOP.
The panel went by really quick and unfortunately, I don't remember most of the questions we were asked (except one likening AOP to Lisp, which offered many features similar to AOP, especially Lisp dialects that offered a Meta-Object Protocol).
I have the feeling we achieved something important last week. There was no bickering about technical details on AOP frameworks nor any personal agendas pushed in outrageous ways. It was a simple exchange of views from people genuinely interested in helping developers write better code,
If anything, we showed the audience that AOP was taken very seriously and considered in very pragmatic terms by a lot of people these days. Whether you think you will be using AOP in your work or not, I strongly recommend you take some time to study its major concepts. I guarantee that even if you day job is to write C code, you will end up reusing these concepts in your own way and your code will greatly benefit from it.