November, 2008

  • The Old New Thing

    The cost-benefit analysis of bitfields for a collection of booleans

    • 68 Comments

    Consider a class with a bunch of BOOL members:

    // no nitpicking over BOOL vs bool allowed
    class Pear {
     ...
     BOOL m_peeled;
     BOOL m_sliced;
     BOOL m_pitted;
     BOOL m_rotten;
     ...
    };
    

    You might be tempted to convert the BOOL fields into bitfields:

    class Pear {
     ...
     BOOL m_peeled:1;
     BOOL m_sliced:1;
     BOOL m_pitted:1;
     BOOL m_rotten:1;
     ...
    };
    

    Since a BOOL is typedef'd as INT (which on Windows platforms is a signed 32-bit integer), this takes sixteen bytes and packs them into one. That's a 93% savings! Who could complain about that?

    How much did that savings cost you, and how much did you save anyway?

    Let's look at the cost of that savings. Code that updated the plain BOOL m_sliced member could do it by simply storing the result into the member. Since it was a normal field, this could be accomplished directly:

      mov [ebx+01Ch], eax ; m_sliced = sliced
    

    On the other hand, when it's a bitfield, updating it becomes trickier:

      add eax, eax        ; shift "sliced" into the correct position
      xor eax, [ebx+01Ch] ; merge "sliced" with other bits
      and eax, 2
      xor [ebx+01Ch], eax ; store the new bitfield
    

    Exercise: Figure out how the above trick works.

    Converting a BOOL to a single-bit field saved three bytes of data but cost you eight bytes of code when the member is assigned a non-constant value. Similarly, extracting the value gets more expensive. What used to be

     push [ebx+01Ch]      ; m_sliced
     call _Something@4    ; Something(m_sliced);
    

    becomes

     mov  ecx, [ebx+01Ch] ; load bitfield value
     shl  ecx, 30         ; put bit at top
     sar  ecx, 31         ; move down and sign extend
     push ecx
     call _Something@4    ; Something(m_sliced);
    

    The bitfield version is bigger by nine bytes.

    Let's sit down and do some arithmetic. Suppose each of these bitfielded fields is accessed six times in your code, three times for writing and three times for reading. The cost in code growth is approximately 100 bytes. It won't be exactly 102 bytes because the optimizer may be able to take advantage of values already in registers for some operations, and the additional instructions may have hidden costs in terms of reduced register flexibility. The actual difference may be more, it may be less, but for a back-of-the-envelope calculation let's call it 100. Meanwhile, the memory savings was 15 byte per class. Therefore, the breakeven point is seven. If your program creates fewer than seven instances of this class, then the code cost exceeds the data savings: Your memory optimization was a memory de-optimization.

    Even if you manage to come out ahead in the accounting ledger, it may be a win of just a few hundred bytes. That's an awful lot of extra hassle to save a few hundred bytes. All somebody has to do is add an icon to a dialog box and your savings will vanished.

    When I see people making these sorts of micro-optimizations, sometimes I'll ask them, "How many instances of this class does the program create?" and sometimes the response will be, "Oh, maybe a half dozen. Why do you ask?"

    But wait, there's more. Packing all these members into a bitfield has other costs. You lose the ability to set a hardware write breakpoint on a specific bit, since hardware breakpoints are done at the byte level (at a minimum). You also lose atomicity: An update to m_sliced will interfere with a simultaneous update to m_peeled on another thread, since the update process merges the two values and stores the result non-atomically. (Note that you also lose atomicity if you had used a byte-sized bool instead of a 32-bit BOOL because some CPU architectures such as the original Alpha AXP cannot access memory in units smaller than a DWORD.)

    These are just a few things to take into account when considering whether you should change your fields to bitfields. Sure, bitfields save data memory, but you have to balance it against the cost in code size, debuggability, and reduced multithreading. If your class is going to be instantiated only a few times (and by "a few" I'm thinking less than a few thousand times), then these costs most likely exceed the savings.

  • The Old New Thing

    Consequences of the Explorer view model: If you create a view, then you succeeded, even if you'd rather fail

    • 60 Comments

    Commenter Anonymous asked why navigating to a drive with no media displays a dialog instead of showing the error message in the view.

    This is an unfortunate consequence of Explorer's browser/view model. The shell browser binds to the IShellFolder and asks for the view by calling IShellFolder::CreateViewWindow. The view window calls IShellFolder::EnumObjects to figure out what to show in the view—and here is where the error dialog appears asking you to insert a disc into the drive.

    The problem is that IShellFolder::EnumObjects has to return an enumerator or an error code. There is no return value that says "Um, yeah, could you display this text instead?" In a narrow sense, there's no way to return it since there is no way to return a string from IShellFolder::EnumObjects, but it's also not possible in a broader sense, since there is no rule that says only shell views can call IShellFolder::EnumObjects. Anybody can bind to a shell folder and enumerate its contents. And most of them don't have any place to display a text message instead of the enumerated objects. For example, the folder tree uses IShellFolder::EnumObjects to fill in children of a node. If you expand a node for an empty floppy drive, where is the "Sorry" message supposed to appear?

    Now, you might say, "Well, make a special case for Explorer," and maybe that's the right thing to do, but designing in a special case to a general interface just for one program tends to create resentment for others: "How come Explorer can do this but my program can't?"

  • The Old New Thing

    Quite possibly my last in-person ballot for a long time

    • 52 Comments

    Most parts of the state of Washington have switched to all-mail voting. No more standing in line at the polling place and casting your vote in person. This is certainly a convenience, but to me, it dilutes the voting experience.

    Part of the experience is the sense that you're part of a process, and standing in a room full of voters certainly drives that point home. You may come from all walks of life, but you all have one thing in common: You all want to vote.

    Also concerning to me is the loss of the guaranteed secret ballot in a mail-in election. With a mail-in ballot, you have the problem that an overbearing family member can dictate how the rest of the family shall vote, and can even oversee the process as the rest of the family members dutifully fill in the dots, then seal and sign the envelope. A family member who wants to cast a vote differently really has no chance. But with an in-person election, the voter goes into a voting booth, and nobody is permitted to go in with that person (with a few exceptions). You know that the vote cast is the voter's true intentions. The overbearing family member has no way of confirming that the vote was cast according to his or her orders.

    (Actually, in my voting district, that's not really true with in-person voting even today. We don't use pull-the-lever voting booths; we use fill-in-the-dots forms, and after filling in the dots, you take your ballot from the voting booth to the scanner. During that walk, the overbearing family member can inspect your ballot to make sure you filled it out "correctly".)

    My voting district is scheduled to switch to all-mail voting next year, and this morning, I stood in line for what is quite possibly the last time. The poll worker for my precinct is a nice Chinese woman. She used to try to speak Mandarin with me whenever I came in, and I would respond with a few set phrases before explaining, "不會說." (Getting the sentence wrong helps drive the point home.) Now she recognizes me and knows better.

    I noted, "Lots of people here today."

    She replied, "Yeah, really busy. More people here now than we used to get all day." She may have been exaggerating, but it was definitely more crowded than it usually is.

    I forgot to say good-bye to her as I left. We may never see each other again.

    (Raymond predicts that the comments will be taken over people discussing electronic voting.)

  • The Old New Thing

    Email tip: If you ask a question that can be answered in only one way, but that's not the answer, don't be surprised that nobody responds at all

    • 51 Comments

    It's not infrequent that I see somebody ask a question that can be answered in only one way. But if that's not the answer, then nobody will respond.

    Is there a module that does XYZ?

    This question can be answered in only one way: "Yes, here it is." If nobody has written such a module, nobody is going to reply saying, "No, nobody has written the module you request," because that would require the responder to prove a negative.

    "I have scoured the entire planet, including code sitting on a hard drive in somebody's mother's basement, and have verified that there is no module that does XYZ. Furthermore, I have altered the rules of the universe to ensure that nobody will write such a module in the time between I completed this investigation and the time you receive this message."

    If you ask a question asking whether something exists, there's only one possible response, because nobody is going to say that the code you request has never been written.

    So far, nothing is wrong. Perhaps the person who asked the question was about to write an XYZ module, but wanted to make sure the effort was not being duplicated.

    However, there are some people who fail to realize that they just asked for proof of a negative, and send a follow-up:

    Resending. Can somebody please tell me whether this module exists?

    What's particularly scary are the people who ask the question in such a way that they are not only asking for proof of a negative, but in fact proof of a perpetual negative. There was one customer who was rather insistent upon receiving an answer to a question of the form "Will there ever be a tool that will...?"

    And once again, the round-up of unhelpful or rude subject lines I've seen in the past five months:

    • Please help
    • Some help please?
    • some help please? [lowercase this time]
    • KB980665 - customer issue!
    • I need urgent help
    • Windows Vista SP1
    • SP1?
    • Need help -- SRS299792458
    • a problem
    • Possible Bug [capital letters make it sound Important]
    • Hi
  • The Old New Thing

    Self-esteem gone overboard: The perils of a global namespace

    • 45 Comments

    There are items with overly generic names. HANDLE, CloseHandle, GetObject, DIFFERENCE, query.exe. But their functionality doesn't live up to their name. HANDLE refers only to kernel handles, CloseHandle can only close kernel handles, GetObject only gets information about GDI objects, DIFFERENCE applies only to the numerical difference between group resources and standalone resources, and query.exe only queries information about Terminal Services Remote Desktop Services.

    Why do functions that operate only inside a specific realm have names that suggest a broader scope?

    Self-esteem gone bad.

    You're on the kernel team. You have a handle manager. What should you call your handles? Well, since they're handles, just call them HANDLE. Because that's what they are, right? And naturally the function that closes HANDLEs should be called CloseHandle. Sure, there are other types of handles out there, but they don't exist in your world. Your world is the kernel, and in the kernel world, you can call them HANDLEs and everybody will know that you're talking about kernel handles because that's why you're in the kernel in the first place! Why would somebody pass a handle to a non-kernel object to a kernel function? That makes no sense!

    Similarly, the GDI folks came up with their own object system, and naturally the way you get information about an object is to call GetObject. There's no confusion here, right? I mean, this is GDI, after all. What other types of objects are there?

    The Terminal Services Remote Desktop Services folks thought the same thing when they created their query.exe program. Hey, this is a computer set up to run Remote Desktop Services; of course you want to query information about Remote Desktop Services.

    Of course, when your symbol exists in a shared namespace, the context of your naming decision becomes lost, and your generic-sounding function name (which worked just great for generic operations in the world in which it was created) ends up carrying more meaning than you originally intended.

    Commenter Sean W. tries to explains that Unix doesn't have this problem. "A Unix-flavored close() system call can close any file descriptor." This explanation ends up being its own counter-argument. When you say that it can close any file descriptor, you're admitting that it can't close anything. You can't use close() to close the objects opened by opendir() or dbm_open() or XtOpenDisplay.

    "Well, yeah, but it can close any file descriptor regardless of where it came from." And CloseHandle works the same way: It can close any kernel handle regardless of where it came from.

    Sean W. later clarified that "the scope of close() is the system kernel, so it's reasonable to expect that it applies to kernel data and no other data, whereas the scope of CloseHandle is all of Win32, including at least KERNEL/USER/GDI/ADVAPI." Um, actually, the scope of CloseHandle is also the kernel.

    And in the category of "suggesting things that are already done" goes this comment from Daniel, who suggests that the documentation explain which HANDLEs can be closed by CloseHandle. Actually, if you look at each function that creates a handle, it also tells you the function to use to close it. Not quite the same thing, but since you have to open something in order to close it, you'll find the information even sooner.

  • The Old New Thing

    The great thing about priorities is that you can always go one higher

    • 42 Comments

    The phenomenon I call priority inflation has spread to product planning documents as well. Back in the old days, there were three priority levels:

    • Priority 1: must have. If you don't accomplish a priority 1 item, you may as well just cancel the project because it ain't shipping.
    • Priority 2: should have. If you don't accomplish a priority 2 item, the product is significantly weaker, but you can still ship it.
    • Priority 3: nice to have. If you don't accomplish a priority 3 item, it's not quite as awesome as it could have been, but it's still a good product.

    Over the past few years, I've seen a shift in the labelling of priorities in planning documents. A new priority has been introduced: Priority Zero. Nobody has explained to me what Priority 0 means, but I assume somebody invented it to emphasize that the feature is even more critical than priority 1. Mind you, I'm not sure what could be more important to a project than "If we don't do this, we're all fired." Maybe "If we don't do this, the earth will explode."

    As you might expect, priority inflation has a trickle-down effect. People whose features had been assigned priority 1 said, "Hey, how come my feature isn't priority 0? It's just as critical as that other guy's feature." Soon, everything that was priority 1 got reclassified as priority 0. Nature abhors a vacuum, so all the priority 2 items got reclassified as priority 1, and the priority 3 items got reclassified as priority 2.

    In the end, nothing changed aside from the names on the buckets. It's been years since I've seen a planning document with any priority 3 items. It's all zero, one, and two now.

    Wait, I lied. The meaning of the last bucket (the former priority 3, now named priority 2) has changed. It used to be things that would be nice to have, but now it appears to be used for something other people suggested which I didn't think was important, but I didn't want to be mean and reject it outright, so I'm listing it here to make those people feel better and showing that their "voice was heard," but don't kid yourself; we're not going to do it. In other words, priority 2 means No.

    I give it three years before somebody decides that an issue is even more critical than priority 0 and labels it Priority −1.

    Epilogue: After I originally wrote this entry, I've learned that some teams have indeed come up with a priority level even more important than Priority 0. It's called Priority Now.

  • The Old New Thing

    What do these topics have in common?

    • 37 Comments

    Update: The first correct answer is from Tom Smith who correctly identified the articles as having ridiculous In Popular Culture sections which mention The Simpsons. Lazbro was right: There needs to be a bot that deletes all "In Popular Culture" sections from Wikipedia.

  • The Old New Thing

    How slow do you have to slow-double-click for it to be a rename?

    • 36 Comments

    In many parts of the system, you can rename an item by first selecting it, then clicking on its name. The selection step is typically done by clicking on the item, which creates the risk that your second click will be interpreted as a double-click rather than as a rename click. How slow do you have to slow-double-click for it to be a rename?

    Slow enough that it's not a regular double-click.

    The double-click time is set in the mouse control panel; I believe the current default is 500 milliseconds. If your two clicks are within a half second of each other, they will be treated as a double-click. If they occur more than a half second apart, then they are treated as two clicks.

    Okay, I lied.

    If you think about it, the algorithm above misses a case: Suppose you click on an item, wait two seconds, and then double-click it. That second click (the first in the double-click) shouldn't initiate a rename because it's really part of a double-click.

    Therefore, the rule really is that a click on a selected item with no other clicks within the double-click time, either before or after is treated as a rename.

    That's why the answer to commenter boxmonkey's question "Who renames files by slowly double clicking?" is "Nobody." It's like asking, "Who makes a telephone call by picking up the receiver and holding the hook down for three seconds before beginning to dial, then holding the hook for another three seconds when the call is over?" Holding the hook isn't part of dialing process. The purpose of holding the hook is to ensure that when you ultimately go off hook, the operation won't be interpreted as a flash. You don't consider it part of the phone dialing process; it's just a way to separate the next call from the previous one.

  • The Old New Thing

    Doesn't matter what your marketing technique is for your compiler if nobody actually writes code in your language any more

    • 34 Comments

    I mentioned Terry Zink's Anti-spam blog ("Protecting your mail from the scum of the internet") during one of my quarterly "borg-edition" linkfests. The article about how much money a spammer actually makes was quite interesting. One thing that caught my eye was the insanely low sales rate that was needed in order to make the enterprise lucrative. Only 0.12% of the messages get clicked on, and of those, only 0.5% result in a sale, yet with a sales rate of just 0.0006%, the spammer pulled down an impressive $7690 per week, or over $300,000 per year. (Researchers who infiltrated the Storm botnet have their own estimates. Terry's story is more interesting to me since it comes from an actual (reformed) spammer.)

    That reminded me of a story told to me by the person who worked on Microsoft's FORTRAN compiler. (Yes, we had one.) He mentioned that one of their attempts to market the compiler was to include a Microsoft FORTRAN business reply card in a targeted mailing to subscribers to a well-known technical computer magazine.

    "Normally, these sort of targetted direct mail efforts generate maybe a 3% or 4% response rate if you do well. We got two."

    — Two percent. Well, that's not too bad, considering this is FORTRAN we're talking about.

    "No, I didn't say two percent. Just two. As in, we received two postcards."

    — Oh.

  • The Old New Thing

    If everything is top priority, then nothing is top priority

    • 34 Comments

    Last time, I mentioned that eventually everything is top priority. A similar topic is what I'm calling priority inflation, which takes more than one form.

    Today's priority inflation is the introduction of new "top priority" items. (Chris Becker has some thoughts on this topic as well.)

    "XYZ is very important to our project. Please make it your top priority." A few weeks later, "ABC is very important to our project. It should take priority over all other issues." When this happens, I like to ask, "Is this even more important than XYZ?" I've done it so much that my management has changed the way it introduces new top priorities: Instead of just saying "Please make ABC your top priority," they list out all the existing top priorities... in priority order.

    ABC is very important to our project. There are just a handful of ABC issues remaining, and we would like to close them out by the end of the month. If you have an ABC issue, please make it your top priority. To summarize:

    1. ABC issues.
    2. XYZ issues.
    3. DEF issues.

    I like this approach because it forces management to understand and acknowledge where their priorities are. If you're going to ship a product, you have to make hard choices, and one of them is deciding where your priorities are.

    If everything is top priority, then nothing is top priority.

    Update: Sometimes, the answer to "Is this even more important than XYZ?" was "No, XYZ is still more important than ABC." So it's not a gimme that if somebody says that ABC is top priority, it replaces what used to be the top priority. That's why it's important to keep track.

Page 1 of 4 (33 items) 1234