Skip to content

World Cup victory celebrations in Mountain View

Went out to brunch in Mountain View right after the match, and a ton of desis were out there having fun!

The smartphone is the territory

I recently had to distribute an item I’d ordered in bulk to a few people across the office. The folks had been given a time, my building and cube number. Our cubes aren’t labeled very well, so I’d stuck a piece of paper with big bold words on it in front of my desk (we have glass walls) to assure people they’d come to the right place.

Person after person came, staring into their phones (we have an app for internal maps), stood right in front of the glass wall and the piece of paper… and nothing registered. Most people kept looking into the phone, with a yearning expression on their face, as if they wished the phone tell them more. A few turned around 180 or 360 degrees on their heels (still staring at their screens), trying to orient themselves.

It’s telling of how much of our lives we’ve boxed-in to a few square inches of space.

Spin locks and the vicious multi-threading cycle

Multithreading is a subject that is really hard for me to keep straight in my head. This is a typical timeline of my neuron activity in any multi-threading topic that’s above absolutely basic.

Time X: Awareness of a sore lack of understanding about topic.

Time X+1: Read the wikipedia article and top few Google search results about the topic. Convince myself that I kinda-sorta understand what it all means.

Time X+2: Promise myself to read up more thoroughly on the topic. After a hurried stack overflow or Google search of how to learn multi-threading, try to bookmark various excellent resources on multi-threading like C# threading, the little book of semaphores or the Java concurrency book. Fail on realizing that all of them are already filed under ‘toread’ in delicious / pinboard.

Time X+3: Berate myself for wasting time.

Time X+4: With 33% probability, read the first chapter of one of the materials above. With exponentially decreasing probability, read the next chapter(s), never getting past the third. In any case, promise myself that when the C++ concurrency book is finally out, I will buy and read it.

Time X+(5…N-2): Real life interrupt.

Time X+(N-1): (Read inspiring but confusing blog post about how company X increased performance by multithreading) OR (come across a tough interview question on multithreading) OR (have a discussion with the significant other about spin locks) OR (…)

Time X+N: Time = Time – N

As you can probably guess, I’m in the penultimate step of that cycle. In an effort to take a little break from it without committing the time needed for reading a book, I’ve decided to write a bit about my understanding of spin locks, hoping it at least helps make N larger.

We need locks to guard against concurrent access to a resource or a value. If an ATM reads a value M for your someone’s bank balance while an account transfer request reads the same value, because if that happens, both the ATM and transfer code would let M dollars be withdrawn, resulting in 2*M dollars where there were only M before. That’s a bug. Except if you’re the Federal Reserve, but that’s another story.

Implicit in the need for locks is the fact that the code we’re running is multi-threaded. That doesn’t imply parallel processing — even on a single-core CPU, multiple threads are being switched in to and out of fast enough to give the illusion of parallel processing. The switching is done either by the kernel, or a thread library, in accordance with some scheduling algorithm.

So when thread X is running some code and requests a resource that is locked by some other thread Y, thread X then has to wait for thread Y to release the lock. Waiting can take two different forms, depending on the locking mechanism. If the resource to be acquired has a spin-lock, thread X must continuously poll a boolean guard variable or flag (e.g. is_locked) until it can acquire the lock, a process known as busy-waiting. Conceptually, this is like the following:

while (true) {
 if (!is_locked) {
   is_locked = true; // acquire lock
   break;
  }
}

// work with lock

is_locked = false; // release lock

In reality the code above won’t work, since the check and subsequent lock acquisition isn’t atomic. Proper busy-waiting usually involves an atomic test-and-set operation which has to be supported in hardware. The upshot, however, is that the thread doesn’t really stop, it keeps looping until the resource in question gets released.

The other option is for thread X to sleep on encountering a locked resource and for the kernel or thread library to resume (wake-up) the thread once the resource is available. This is how most multi-threading primitives like mutexes or condition variables operate. Unlike spin-locks, in this case, the thread is not scheduled to run until there is a change in the status of the resource which it was requesting.

Which one is better depends primarily on how long the expected wait time is. On the face of it, spin-locking seems more expensive as the thread keeps running (and therefore consuming CPU cycles) even while waiting; whereas a thread encountering a mutex-locked resource goes into the background until it can do useful work, freeing up the CPU to work on other tasks. There are costs associated with the latter, though; the cost of putting the thread on the suspend queue and bringing it back, and the cost of the kernel keeping track of the resource state in order to wake up the suspended thread. If your thread expects to have an extremely short waiting time, then, a spin-lock may be more efficient.

I don’t have a very good idea of the numbers involved, but a good lower bound for a thread state change is the time it takes to do a context-switch, which is on the order of a few hundred CPU cycles; a really short period of time, about the same as RAM latency. A disk seek, by comparison, has a latency measured in millions of cycles (see this excellent article for more info). The bottom line — you shouldn’t be using spin-locks unless you’re writing very low level code and know exactly what you’re doing; but in that case you don’t need me to be telling you these things!

The economics of the D7000 kit

Simply put, the Nikon D7000 is the best value-for-money DSLR Nikon has manufactured till date. It’s the perfect time to upgrade for me as well, the only hitch being — the body-only version isn’t in stock anywhere. Nikon sees fit to keep the supply of the “bundle” with the 18-105 mm lens in stock.

Very few people will buy a Nikon D7000 as their first DSLR. The biggest audience for this camera is either folks like me — I’ve been shooting a D80 for four years and am looking to upgrade; or the super-enthusiast or professionals looking for a solid second body. Neither group will care for the 18-105; but both will badly want their hands on a D7000. An excellent opportunity for Nikon to get rid of some 18-105 lenses.

No surprise to see that the “used” section of the 18-105 lens is full of people wanting to get rid of their kit lens.

Turn off Google Instant Preview (without installing stuff)

Google search has a new feature called “Instant Preview” which pre-fetches search results pages and displays them in a preview pane when you hover over a search result. I suppose it could be argued that this is helpful, but many (including me) find it irritating.

To toggle instant previews on or off, all you have to do is click anywhere on a search result snippet (or click once on the blue magnifying glass). That will prevent instant previews from automatically popping up, or re-enable them if you had turned them off.

Somehow a lot of mainstream sites seem to recommend using adblock, greasemonkey or other plugins — but they’re not needed just for disabling instant previews.

The Value of Nothing, by Raj Patel

Most of the economic literature that I read tends to fall into two neat categories — dense and nearly incomprehensible, or overly simplistic soundbite material. Fortunately, I’m getting better and picking up books that go into depth but are still understandable. Raj Patel’s brilliant book falls into this category.

The main thrust of the book is that contrary to popular capitalist beliefs, markets aren’t efficient at pricing everything. Although believing that markets are in general a good thing in many areas, he proves by way of theory and example that applying capitalism to every area of society and life leads to the old adage of people ‘knowing the price of everything and the value of nothing.’

The bit that stayed with me was that in a capitalist system, the price of an entity is linked to its marginal returns and not its long term value. Limited natural resources are an excellent example. Take natural freshwater, for example. Water is cheap (for now) because there are places where its abundant and the market determines the price using supply and demand — a business entity in a competitive environment can make a profit by extracting and selling it cheaply. Whether there is a millennium’s worth of freshwater in a particular place or only a decade’s worth actually makes little difference to the price. The fact that the depletion of freshwater might threaten an entire community’s survival is irrelevant to the market economy, as long as it’s viable to profit from the resource in the medium term.

This discussion leads directly to the book’s central thesis, the importance of the “commons”. Entities that are essentially public goods that should be publicly regulated and not opened to the free market. A classic example here is the fishing industry, which in many places was severely threatened by overfishing until government regulations mandated limits. He goes further, though, and talks about how a huge class of poor peasants was created by the handing over of public lands to private owners. People who earlier could forage, hunt and fish for their own livelihood now had no choice but to sell their labour in exchange for resources to survive.

Yet another contribution of the book is examples of how commons-based systems are actually working in today’s world, like Via Campesina, Participatory Budgeting and the Deccan Development Society. The book also mentions the Kingsnorth Six case, in which a British Court acquitted six people who had substantially damaged a coal-fired power plant; and pleaded not guilty by basically saying they were saving the planet.

Patel takes fascinating dives into subjects like the theories of Keynes and Marx, and the principles behind the Magna Carta and English common law. All of it is eminently readable, and I’d love to sometime go back to the book and imbibe the details more thoroughly.

A useful C++ interview question

It’s surprising how few people who say they know C++ really know C++. This is my favourite basic C++ interview question.

Lets say you want to write your own, simple fixed-size vector class for integers. The specification is simple — construct the vector with one argument, the size of the vector. Construction creates a vector of the given size, all initialized to zero. Support accessors via indexing.

Here’s the first try (which I write on the whiteboard for the candidate):

#include "stdio.h"
#define OUT_OF_RANGE 1

class Vec {
  public:
    Vec(int sz) : sz_(sz) { 
      data_ = new int[sz_]; 
      for (int i=0; i != sz_; ++i) { data_[i] = 0; }
    }

    ~Vec() { delete data_; }

    int size() { return sz_; }

    int& operator[](int i) {
      if (i < sz_) return data_[i];
      else throw OUT_OF_RANGE;
    }

    int sz_;
    int* data_;
};

int main() {
  Vec v(10);
  int i;
  for (i = 0; i != 10; ++i) v[i] = i+1;

  // this prints "1 2 3 4 5 6 7 8 9 10"
  for (i = 0; i != 10; ++i) printf("%d ", v[i]);
}

The question is this. The code, with a basic test, compiles and works as you might expect. Is there anything wrong with this code?

If your candidate stares at this and says “looks OK to me”, it’s probably time to end the interview and send them home. The correct answer, of course, is “many, many things.”

No encapsulation. The members sz_ and data_ should be declared private, otherwise clients could corrupt the data, intentionally or otherwise.

The destructor won’t delete the allocated array. It should say delete [] data_;. If they don’t know this, they have no idea of C++’s memory model.

It’s a mistake to use an integral size, since integers can be negative. In the given code, if you give a negative integer parameter to the constructor, new will throw an exception, or even if it doesn’t the for loop will be infinite. If you call an accessor with a negative index (v[-2]), it’ll access illegal memory. The size parameter should ideally be std::size_t, or at least unsigned.

The compiler will auto-generate crash-inducing code for copy construction and assignment, since these haven’t been defined. For example, the auto-generated assignment operator will look like this:

Vec& operator= (const Vec& rhs) {
  this.sz_ = rhs.sz_;
  this.data_ = rhs.data_;
  return *this;
}

Note that this copies the pointer to the array and not the array. The simple act of adding Vec v2(10); v2 = v1; at the end of the main function above will cause delete to be called twice on the same pointer, when v1 and v2 are destructed, leading to potential disaster. The candidate should be able to code both functions correctly.

You can’t use a const Vec object or reference for read-only operations, which basically cripples the class. If you want to pass a Vec to a function that only reads it, func(Vec v) results in an expensive copy operation, and func(Vec& v) or func(Vec* v) doesn’t guarantee that the vector won’t be mutated. Whats needed is to mark the size() function as const and add a const accessor:

const int& operator[](std::size_t i) const { 
  /* same code as non-const */
}

An implicit constructor could lead to uncaught bugs at compile time. For example, a function with the signature myFunc(Vec v) could be called as myFunc(5) with an implicit Vec object being constructed as the argument. In almost all cases, this is unintentional and erroneous, and the constructor should be marked with the explicit keyword.

What I like about this question is that the quality of the candidate’s answers tell you a lot. Some candidates will surprise you and go beyond the basic issues listed above. If a candidate gets through these quickly, that’s a very good sign and you can go on to further improving the design, using templates, dynamic re-allocations etc.

Introducing write-only

Writing has become harder for me over time, evidenced by the dropping frequency of posting here over the last few years. Every now and then I resolve to fix the situation, which usually results in nothing more than a short-lived spurt of words. I think the only strategy that has remotely been successful is my decision to write reviews about the books that I read here.

As time has passed, I see an increasing need to reduce distractions while writing. At one point, I would happily compose a post in the Blogger or WordPress native web interface. For the past year or two, however, I’ve noticed that I could only write in a plain text editing tool with no interface clutter, like good old Notepad.

Recently, I started using Writeroom (or its equivalent, Darkroom on Windows) for writing. A full-screen text-only editor suddenly made a lot of sense. I was even more excited when I found out about textarea, a really clean writeroom-like interface on the web. It’s a basic HTML/js file that I thought was the perfect interface for writing. Unfortunately, it was client-side only.

Thankfully, I had a week of unemployment between jobs, so I wrote a web app that adds a back-end to the textarea interface. It’s at http://write-only.appspot.com and I’m using it to write this very post. It’s open to anyone: you’ll need a google account to sign in, since I used Google’s App Engine for making it.

It’s striking how much easier web programming has become. The last time I did any of this stuff was during my graduate school days, and then I was just interested in getting some user input over the web to use as parameters for a long computation on the back-end. I could’ve nominated my design for the worst web user-interface design ever award!

P.S. This is a purely personal project and doesn’t have the endorsement of my employers in any way, shape or form.

The Hungry Tide, by Amitav Ghosh

Set in the mysterious, dangerous and constantly changing terrain of the Sunderbans in East India and Bangladesh, this gripping tale of young woman’s journey unfolds spectacularly with all the drama of a Shakespearean play and mythological echoes of the great Indian epics.

A young Indian born American marine biologist, Piyali Roy journeys to the Sunderbans to study their unique marine life. To help her navigate the rough seas and terrain, she engages a fisherman, Fokir who doesn’t speak English but has an almost mystical knowledge of the lay of the land and sea. She also runs into Kanai Dutt, an urbane, suave and witty character who happens to be visiting his aunt in the Sunderbans and goes along with the mission out of a sense of intrigue and a personal interest in our heroine. The interplay between the three is masterful, but the story is set on two levels. Kanai’s widowed aunt has found old documents that describe events three decades earlier, a struggle between Indian authorities and settlers in the Sunderbans region. The tale of the refugees fighting for their political rights years ago interspersed with the storms that Kanai, Piyali and Fokir battle make this a truly breathtaking piece of literature.

I don’t read much fiction these days, but I picked this book up and was floored by it. I heartily recommend a read.

Curfewed Night, by Basharat Peer

“There are no good stories in Kashmir. There are only difficult, ambiguous, and unresolved stories.”

This line from Curfewed Night perfectly captures the message of the book. Basharat Peer tells an enchanting, if sad, tale of his childhood and youth in the Kashmir valley. The struggles of its people walking a thin line between two two-faced sides: the freedom-fighters who can be terrorists; and the democratic rulers who can be oppressors. In a land as charged up as Kashmir, every sip from the cup of life — growing up, choosing a profession, educating a child, speaking your truth — is laced with the dreaded poison of navigating a maze of choices between competing politics.

The wistful, lyrical references to Kashmir’s natural beauty woven throughout the story only serve to make it all the more heart-wrenching. How tragic that a place still referred to as “Heaven on Earth” should go through such hell.

The book serves as a sober reminder of the value of freedom, which so many of us from India enjoy without savouring. How hard it is for a people to come to a consensus on what represents freedom and how it is best achieved. People who talk about Kashmir only in black-and-white terms of terrorism or government oppression should take some time and think about that.