Gray Areas In Java

In case you ever wondered what weak and soft references are in Java, here are couple good articles explain what they are and when you might use them:

• Plugging memory leaks with weak references
• Plugging memory leaks with soft references

Forward Declarations And Faster Compilations

In C++, a Forward Declaration is a declaration of a type that occurs before the definition of that type. For example, suppose you write the small program:
#include <iostream>

int main(void) {
  doSomething();
  return 0;
}

void doSomething(void) {
  std::cout << "Hello World!" << std::endl;
}

This program, won't compile - you'll get an error like dosomething.cc:4: error: `doSomething' undeclared (first use this function) because doSomething() is called in the source code (line 4) before it is visible (line 8 onwards).

The simplest way to fix this is to simply switch the order that main() and doSomething() appear in the file. i.e.
#include <iostream>

void doSomething(void) {
  std::cout << "Hello World!" << std::endl;
}

int main(void) {
  doSomething();
  return 0;
}

Another way to correct the file is to use a forward declaration of doSomething(). i.e.
#include <iostream>

// forward declaration
void doSomething(void);

int main(void) {
  doSomething();
  return 0;
}

void doSomething(void) {
  std::cout << "Hello World!" << std::endl;
}
The (potential) advantage of this approach is that it gives you the ability to layout the order of the file as you see fit (e.g. to make it more readable) while satisfying the compiler (language requirements).

Now consider the following larger example with three classes:
Name.h
#include <string>

class Name {
  public:
    Name(const std::string & firstName, const std::string & lastName);

    std::string getFirstName() const;
    std::string getLastName() const;

  private:
    std::string _firstName;
    std::string _lastName;
};

EmailAddress.h
#include <string>

class EmailAddress {
  public:
    EmailAddress(const std::string & emailAddress);

    std::string getEmailAddress() const;
    std::string getDomain() const;

  private:
    std::string _userName;   // e.g. "JohnSmith" part of "JohnSmith@gmail.com"
    std::string _domain;    // e.g. "gmail.com" part of "JohnSmith@gmail.com"
};

Person.h
#include "EmailAddress.h"
#include "Name.h"

class Person {
  public:
    Person(const Name & name, const EmailAddress & emailAddress);

    const Name & getName() const;
    const EmailAddress & getEmailAddress() const;

  private:
    const Name & _name;
    const EmailAddress & _emailAddress;
};

Person.cpp
#include "Person.h"

Person::Person(const Name & name, const EmailAddress & emailAddress)
  : _name(name), _emailAddress(emailAddress)
{
  // empty
}

// etc.

NameFunctions.cpp
#include <iostream>
#include <vector>
#include "Person.h"

void printFirstNames(const std::vector< Person > & persons) {
  for( std::vector< Person >::const_iterator iter = persons.begin();
      iter != persons.end(); ++iter ) {
    std::cout << (*iter).getName().getFirstName() << std::endl;
  }
}

Notice how Person.h includes both Name.h and EmailAddress.h. Consider what happens when NameFunctions.cpp is compiled. The preprocessor must replace the include of Person.h with the contents of that file. To do this, the preprocessor first recursively includes the contents of Name.h and EmailAddress.h in Person.h since Person.h includes these two files. Therefore, to build NameFunctions.cpp, four files must be loaded and processed - NameFunctions.cpp as well as its includes (Person.h) and the includes' includes (Name.h and EmailAddress.h).

Similarly, consider what happens when you change EmailAddress.h and then run a program like make to recompile any impacted source code. Make will consider all the files that could be affected by this change, of which NameFunctions.cpp is one of those files! (It consumes EmailAddress.h indirectly, as shown above). Likewise, when you are computing the files that depend upon EmailAddress.h, the calculation is non-trivial since you need to traverse from EmailAddress.h to Person.h to NameFunctions.cpp.

So what do all these includes mean for your compilation times?

• Compiling a source file involves loading a lot of header files into memory (and not just all the ones listed in the source file; but the includes' includes, the includes' includes' includes, etc.), which can be many more files than you would suspect. In a large project, you are going to have a lot of these files, and they will be scattered across your disk and each will be used only some of the time. i.e. The limited locality and large input set won't be favourable to caching and the hard drive could be hit often (which is slow).
• Dynamically figuring out dependencies is costly, since the graph of related files has a lot of edges. (And this can, again, involve lots of disk accesses).
• Dynamically figuring out what dependencies have changed since you last ran make is expensive because the dependencies are expansive. (Again, lots of disk accesses).
• When you change a header file, there will be a cascading effect of rebuilding a lot of source files.

Now, is all this work really necessary? First notice, that NameFunctions.cpp technically depends on EmailAddress.h (since Person.h does), but NameFunctions.cpp only really uses the Person and Name classes (but not the EmailAddress class). Next, notice that the definition of Person in Person.h only uses references to Name and EmailAddress. Hence, the compiler only needs to know that Name and EmailAddress are classes when it processes Person.h, but not the substance of those classes. (As the references are really just memory addresses, i.e. 1 word, the memory layout of Person is independent of the contents and interface of these two classes). Therefore, we can replace the two lines in Person.h:
  #include "Name.h"
  #include "EmailAddress.h"
with the lines:
  // forward declarations
  class Name;
  class EmailAddress;.
And the start of NameFunctions.cpp must now be changed from
  #include "Person.h" to
  #include "Person.h"
  #include "Name.h"
(as the function in this file invokes Name::getFirstName(), a forward declartion does not suffice, it needs to know the definition of Name).

What are the consequences of these changes? The code still compiles, but faster:

• Compiling NameFunctions.cpp no longer involves loading EmailAddress.h.
• Figuring out the dependencies of NameFunctions.cpp is simpler because there are less dependencies (and they are likely more stable).
• Figuring out what files need to be recompiled is less costly because there are less dependencies to examine.
• Rebuilding the affected source code after a change to EmailAddress.h is less work because the (falsely) dependent file NameFunctions.cpp no longer needs to be built.

In addition to slower compiler times, using includes in headers (instead of forward declartions) can cause other problems. e.g. Suppose A.cpp uses the class C, but gets it indirectly via including B.h instead of C.h

• What happens if B.h is changed to no longer include C.h? Then A.cpp no longer compiles, an unfortunate side effect. Hence, the code (without forward declarations) is brittle and not self-documenting (as A.cpp's dependency on C.h is not explicit).
• Also, dependencies are more likely to be properly calculated. If your dependency calculation is shallow (i.e. it determines that A.cpp depends upon B.h, but not that A.cpp depends upon the dependencies of B.h, such as C.h) What happens if the definition of C changes in C.h? A.cpp will not be recompiled and the resulting program execution is likely to exhibit bizarre behaviour (i.e. if C's v-table was altered).
• Searching for dependent files by using a command like grep "#include \"C.h\"" will be miss finding A.cpp.

Memories of 342

Building a better HashMap is a short, but interesting, article on IBM's website about how java.util.concurrent.ConcurrentHashMap is implemented to provide much efficient concurrency than java.util.Hashtable.

Good Agile, Bad Agile

I just finished reading Steve Y's Good Agile, Bad Agile. I think this anecdote was my favourite part:

Most engineers are not early risers. I know a team that has to come in for an 8:00am meeting at least once (maybe several times) a week. Then they sit like zombies in front of their email until lunch. Then they go home and take a nap. Then they come in at night and work, but they're bleary-eyed and look perpetually exhausted. When I talk to them, they're usually cheery enough, but they usually don't finish their sentences.

Work

Working at Microsoft is an interesting essay. (It's one of the many articles I bookmarked and took forever to get around to reading, so I'm not sure where I found it). I can relate to many of the points in it. I especially liked the subsection "Managers". The statement "...the Seattle area is known for being somewhat isolating — lots of young, ambitious professionals with no time for making friends..." is also too true.

CRC

In case you ever wondered how CRC worked (or how to use what you learned in Polynomials, Rings and Finite Fields), Cyclic Redundancy Check gives a short description of the math behind CRC as well as how to implement it as an algorithm.

Building a Better Voting Machine

Building a Better Voting Machine is a short and interesting article about voting machines (via Slashdot).

I've been meaning to print a copy of Rivest's Third Ballot Voting System and read it while I take the bus to work, but I haven't gotten around to it yet.

Learn Ruby Or Python?

I've been reading a lot of short computer-programming articles online lately, such as Exception-Handling Antipatterns, which I bookmarked a couple weeks ago (as a possible reference for a talk about Defensive Programming that I gave two weeks ago), but didn't end up reading it until today.

I also learn about Duck Typing (via Joel on Software's Ruby Performance Revisited). The articles The Perils of Duck Typing and Java does Duck Typing were interesting follow-ups.

I think I need to get around to learning Ruby. I've been meaning to for a while, but have never gotten any farther than bookmarking Prgramming Ruby and Why's Poignant Guide To Ruby. Do you think I should teach myself Ruby or try learning Python first?

Mount Si

I went hiking up Mount Si yesterday with Sudhanshu. It was my third time hiking up to the top. I can tell that I'm in better shape then the previous times, but it was still quite grueling (and my knees are a bit sore today). The weather was little hazy, but the view from the top was good.

I'll post some photos once I install a new hard drive. (My current one is a bit small and full of music and photos).


And is it just me or does the Joliet file system suck. Why can't perfectly valid filepaths from a FAT or NTFS drive be copied onto a CD as is. Is that too much to ask?

The Electronic Frontier Foundation (EFF)

Defending liberties in high-tech world [MSNBC] is a good description of what the Electronic Frontier Foundation (EFF) is all about. (Via Slashdot)

How To Be Silicon Valley

Another interesting Paul Graham essay: How To Be Silicon Valley (via Slashdot).

His link to an urban sprawl photo (and the photo's caption) made me laugh.

Are Software Patents Evil?

Patent trolls are companies consisting mainly of lawyers whose whole business is to accumulate patents and threaten to sue companies who actually make things. Patent trolls, it seems safe to say, are evil. I feel a bit stupid saying that, because when you're saying something that Richard Stallman and Bill Gates would both agree with, you must be perilously close to tautologies.

Are Software Patents Evil? is (another) well-written essay by Paul Graham. (It even uses hockey as a metaphor!)

Who Can Name The Bigger Number?

Who Can Name The Bigger Number? (via Metafilter).

...

Ackermann numbers are pretty big, but they’re not yet big enough. The quest for still bigger numbers takes us back to the formalists. After Ackermann demonstrated that ‘primitive recursive’ isn’t what we mean by ‘computable,’ the question still stood: what do we mean by ‘computable’? In 1936, Alonzo Church and Alan Turing independently answered this question. While Church answered using a logical formalism called the lambda calculus, Turing answered using an idealized computing machine—the Turing machine—that, in essence, is equivalent to every Compaq, Dell, Macintosh, and Cray in the modern world. Turing’s paper describing his machine, "On Computable Numbers," is rightly celebrated as the founding document of computer science.

...

"Very nice," you say (or perhaps you say, "not nice at all"). "But what does all this have to do with big numbers?" Aha! The connection wasn’t published until May of 1962. Then, in the Bell System Technical Journal, nestled between pragmatically-minded papers on "Multiport Structures" and "Waveguide Pressure Seals," appeared the modestly titled "On Non-Computable Functions" by Tibor Rado. In this paper, Rado introduced the biggest numbers anyone had ever imagined.

...

I miss 365.

Programming Languages

Programming languages and their relationship styles (via Funkaoshi) .

Great Design

Joel on Software has started a series of articles on Great Design.

The Pragmatic Programmer

I finished reading The Pragmatic Programmer a couple weeks ago. (And have been meaning to mention it, but kept forgetting). The book outlines an approach to software development summed up by its first "tip": Care About Your Craft - Why spend your life developing software unless you care about doing it well?

What you learn in school tends to be either aspects of Computer Science or the syntax and features of various programming languages. Both are useful, but developing software and working with complex systems have many other facets, many of which are best learned though experience. The book is a collection of short chapters that discuss what the authors' have learned about the later.

The engineering process - creating maintainable and testable software, design, documentation, and debugging - receives a lot of coverage. But other engineering topics and skills, including tools, architecture, communication, scoping and estimation, as well as career development, are discussed. The writing style is clear and full of examples, but concise (in a good way).

I highly recommend this book as it will (likely) introduce many new and helpful ideas as well as solidifying things that you may have learned along the way but aren't quite sure how to articulate or reason about.

How to Do What You Love

How to Do What You Love is an thought-provoking essay by Paul Graham. [Via Funkaoshi].

Finding work you love is very difficult. Most people fail. Even if you succeed, it's rare to be free to work on what you want till your thirties or forties. But if you have the destination in sight you'll be more likely to arrive at it. If you know you can love work, you're in the home stretch, and if you know what work you love, you're practically there.

Right now there are things I like about my work, but there are also things I really hate. So I don't think I'm doing what I love. I'm not even sure that my destination is in sight yet. I guess this is something else that I'll need to reflect upon. (e.g. If I decide to go to grad school, applications for fall 2007 are more or less due this fall).

Dancing Links

One of my co-workers forwarded me a copy of Dancing Links by Donald Knuth. In the paper, Knuth describes a backtracking algorithm, DLX, for solving exact cover problems using a doubly-linked-list type data structure. As the algorithm recursively searches for possible solutions, the links in the lists that represent the problem "dance" as they are updated from previous candidate solutions to reflect the candidate solution that is currently under consideration.

What is the exact cover problem? Given a set of elements U and a collection S of subsets of U, an exact cover C of U is a subset of S so that each element of U appears in exactly one of the subsets in C.

For example, suppose U = { 1, 2, 3, 4, 5 } and S = { S₁ = ( 1, 5 ), S₂ = ( 1, 2, 4 ), S₃ = ( 2, 3, 5 ), S₄ = ( 2, 4 ), S₅ = ( 1, 4 ), S₆ = ( 3 ), S₇ = ( 4 ) }. Then an exact cover of U is { S₁, S₄, S₆ } since together these three sets have all of the elements U = { 1, 2, 3, 4, 5 } and no elements appears in more than one of S₁, S₄, S₆. Similarly, { S₃, S₅ } is another exact cover. On the other hand, { S₁, S₃, S₇ } is not an exact cover because 3 appears in both S₁ and S₃. Likewise, { S₂, S₆ } is not an exact cover because neither S₂ nor S₆ contains 5.

Suppose you are given a chessboard (an 8 x 8 grid) and 32 dominos (2 x 1 rectangles), which have squares of the same size as the chessboard. Can you place the dominos on the chessboard so that each square of the chessboard is cover? Yes; and it should be straightforward to do! (e.g. Make a row of four dominos that are horizontal. That will cover one of the ranks of the chessboard. Simply repeat this seven more times). Now, what happens if I give you 31 dominos and cut away the top left (a8) and bottom right (h1) squares of the chessboard (so it has 30 white and 32 black squares). Can you cover this modified chessboard with your 31 dominos?

If the domino and chessboard example still sounds too contrived then consider how you would write a computer program that can solve Su Doku problems. [Hint: Dancing Links!]

Data Mining

Business Week has an article, Math Will Rock Your World, that discuess data mining and using mathematics to model and improve business processes (e.g. supply chain optimization).

... This mathematical modeling of humanity promises to be one of the great undertakings of the 21st century. It will grow in scope to include much of the physical world as mathematicians get their hands on new flows of data, from atmospheric sensors to the feeds from millions of security cameras. It's a parallel world that's taking shape, a laboratory for innovation and discovery composed of numbers, vectors, and algorithms. "We turn the world of content into math, and we turn you into math," says Howard Kaushansky, CEO of Boulder (Colo.)-based Umbria Inc., a company that uses math to analyze marketing trends online...

Assorted Math & Technology News

When I started studying at the University of Waterloo's Faculty of Mathematics, Comptuer Science was a (very large) department. About halfway through my studies, it became the School of Computer Science. I read a couple days ago that David Cheriton, an alumnus and professor at Stanford donated $25 million to the School so the University renamed it to become the David R. Cheriton School of Computer Science. (How does a university professor become a multimillioniare you ask? They finance Google in 1998 with $200 thousand in seed money, which is, of course, the definition of ROI).

I heard from my Mom that the Ontario Government is planning on dropping Calculus from it's high school curriculum. That's not very wise.

Lastly, The New Yorker has an interesting article, Blackberry Picking, about patents. In particular, it addressed the RIM v. NTP proceedings. It's concise and very well written. It's worth reading.