Wednesday, August 03, 2011

g++ unordered_multimap: an exercise

I discovered this randomly several weeks ago while debugging something else at work, and I thought it was worth sharing since the g++ STL is widely used.

Step 1: Save the following file as mapdemo.cpp:

#include <iostream>
#include <unordered_map>

int main() {
    typedef std::unordered_multimap<int, int> int_multimap;
    int_multimap map;
    for (int i = 0; i < 10000; ++i) {
        map.insert(int_multimap::value_type(17, i));
    std::cerr << *static_cast<int*>(0);
    return 0;

Step 2: Compile the file:

g++ --std=c++0x -g mapdemo.cpp

Step 3: Load the file in gdb and examine the buckets:

$ gdb -silent ./a.out
Reading symbols from xxx/a.out...done.
(gdb) run
Starting program: xxx/a.out 

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400b4d in main () at mapdemo.cpp:10
10     std::cerr << *static_cast<int*>(0);
(gdb) p map._M_bucket_count
$1 = 15173
(gdb) p map._M_buckets[0]
$2 = (std::__detail::_Hash_node<std::pair<int const, int>, false> *) 0x0
(gdb) p map._M_buckets[15172]
$3 = (std::__detail::_Hash_node<std::pair<int const, int>, false> *) 0x0
(gdb) p map._M_buckets[17]
$4 = (std::__detail::_Hash_node<std::pair<int const, int>, false> *) 0x605080
(gdb) p *map._M_buckets[17]
$5 = {_M_v = {first = 17, second = 0}, _M_next = 0x670c90}

Yes, g++'s implementation of unordered_multimap (known as hash_multimap in pre-C++0x versions of C++) uses bucket hashing, but the size of the backing array is proportional to the count of elements in the multimap, not the count of distinct keys.

Exercise for the reader: Explain what I just did; explain why the result of step 3 is curious; and then explain why the authors might have chosen to do it this way anyway.

It occurs to me that this would have made a decent interview question if I hadn't written it up here. Oh well, I have others.

Monday, August 01, 2011

Acer Aspire TimelineX 1830T semi-review

Attention conservation notice: Google-food for a gadget you will probably never need to know about.

I recently bought an Acer 1830T ultra-compact notebook (11.6" screen, 3.1 lbs, Core i5 470UM, ~$540 street price). I have neither the time nor (yet) the data to review it comprehensively, but here are a few observations that I didn't find in other online reviews, with a focus on the physical design. This review is intended to complement other information online, not replace it, and is offered in the hope that it's useful to other people who may be in the market for a very small laptop.


You can read on the spec sheet that the laptop is 285 x 204 x 28 mm (11.22 x 8.03 x 1.1 inches) at its widest point, but that doesn't give you a visceral feel for its size. Here it is next to a few objects with which you may be familiar.

Counterclockwise from upper left: Kindle 2G, 12oz. Diet Coke, Nexus S, $1 Federal Reserve Note, 15" Macbook Pro (unibody), and TimelineX 1830T. You can see that it's quite small. It feels qualitatively similar in the hand to other ultra-compact notebooks I've handled, such as smaller Lenovo X series laptops, although it's not nearly as blade-thin as a Macbook Air. Below are a couple of detail on-edge shots to illustrate the device thickness.

The top shot is the same 15" Macbook Pro and Kindle stacked next to the TimelineX 1830T, with the other props on the edges. The bottom shot is the Macbook Pro alone next to the 1830T. Subjectively, I will say that its small size and light weight make it feel thinner than it is. I'll toss this in my bag as a second laptop without hesitation.

Input devices

The keyboard is OK but not stellar. Here it is, compared to the Macbook Pro keyboard, using my left hand as a reference object:

You'll notice that it's marginally smaller — and for me, this is enough that it does subjectively feel more cramped — but it's much closer than I would have expected, and about as good as I'd expect from a machine this size. It's not a Lenovo keyboard but then nothing is.

The trackpad is quite small and almost invisible, marked only by three fine raised lines on the palmrest's metal surface:

Overall the small size of the palmrest and trackpad are the biggest ergonomic shortcomings of this device. I've concluded that they shrunk the palmrest to make room for the (huge) battery on the top side of the keyboard. After a brief acclimation period, I find the trackpad acceptable for casual use, but I expect I'll still carry around a mouse when I want to do serious work.

Power adapter

The TimelineX has an interesting power adapter. First, here is a size illustration.

Counterclockwise from upper left: Nexus S, Macbook Pro power adapter, TimelineX 1830T power adapter, 12oz. Diet Coke, and $1 bill. Note that the adapter is closer in size and weight to a cell phone power adapter than a traditional laptop power adapter. Furthermore the plug prongs are detachable:

Cleverly, the prongs can be attached in either orientation:

Obviously this is useful for power strips or other situations where the area around the cord might be crowded. Most laptops deal with this problem by attaching the plug head via a separate cord, but I would like to see this design become more widespread for cell-phone-style power adapters. Rotating the prongs is a simple 10-second operation:


A few other brief observations:

  • 1080p video plays perfectly fine, either downsampled on the native 1366x768 screen or at full resolution on an external 1080p television via HDMI.
  • 64-bit Ubuntu Maverick (10.10) under VMWare Player works adequately for casual coding. I have not yet set up dual-boot and perhaps I won't need to.
  • Suspend from resume is quite quick in Windows; a full boot is slow but rare.
  • The battery is huge; the screen is small; the CPU is an ultra-low-voltage Core i5. The net result is that battery life goes all day for practical purposes, and this is the rare laptop that I will not bother to plug in during use most of the time.

Finally, here's a close-up shot of the laptop cover, which has a nice, grippy embossed cross-hatched texture.

p.s. Incidentally, having shopped for a laptop recently, I have to say that typical review sites do not pay nearly enough attention to laptops as physical objects. The physical reality of the laptop is one of its most crucial characteristics; it's not like a workstation which you just leave under your desk and hook up to the keyboard, mouse, and monitor of your choice. People who do this for a living should be able to provide more useful and objective information than "it feels light". Also, laptop review sites overall strike me as quite lazy. Why would you show useless white-background product shots from the PR kit, when digital cameras are so ubiquitous, and it's trivial to take your own much more useful photos, as this blog post shows? Grrr.