• The Old New Thing

    Displaying the dictionary, part 3: Using an owner-data listview

    • 26 Comments

    Owner-data listviews let you take over data management from the listview. This is useful in our case since we have over twenty thousand dictionary entries, and creating even that many blank listview items takes an unacceptably long amount of time.

    Let's convert our listview to an owner-data listview. Believe it or not, this is quite easy to do once we have the text callback technique from last time. Make the following changes:

    LRESULT RootWindow::OnCreate()
    {
      m_hwndLV = CreateWindow(WC_LISTVIEW, NULL,
                      WS_VISIBLE | WS_CHILD | WS_TABSTOP |
                      LVS_NOSORTHEADER | LVS_OWNERDATA |
                      LVS_SINGLESEL | LVS_REPORT,
                      0, 0, 0, 0,
                      m_hwnd,
                      (HMENU)IDC_LIST,
                      g_hinst,
                      NULL);
     ...
     // for (int i = 0; i < Length(); i++) {
     //  const DictionaryEntry& de = Item(i);
     //  LVITEM item;
     //  item.mask = LVIF_TEXT;
     //  item.iItem = i;
     //  item.iSubItem = COL_TRAD;
     //  item.pszText = const_cast<LPWSTR>(de.m_pszTrad);
     //  item.iItem = ListView_InsertItem(m_hwndLV, &item);
     //  if (item.iItem >= 0) {
     //   item.iSubItem = COL_PINYIN;
     //   item.pszText = const_cast<LPWSTR>(de.m_pszPinyin);
     //   ListView_SetItem(m_hwndLV, &item);
     //   item.iSubItem = COL_ENGLISH;
     //   item.pszText = const_cast<LPWSTR>(de.m_pszEnglish);
     //   ListView_SetItem(m_hwndLV, &item);
     //  }
     // }
     return 0;
    }
    

    That's right, we made things better by deleting code. Isn't that satisfying?

    Owner-data is like the text callback mechanism in the extreme: The listview doesn't record any information about the contents of your items. Whenever it needs something, it always asks. To create twenty thousand items, we just call ListView_SetItemCount and tell it that there are twenty thousand items. (There is also a ListView_SetItemCountEx macro which lets you pass flags, none of which are relevant here.)

    In many owner-data cases, the data comes from an external source, in which case the LVN_ODCACHEHINT notification can be helpful. The listview sends this notification to say, "I'm going to be asking a lot of questions about items in this range. You might want to go work on them." Note that the listview might ask questions about items outside the range, too. The notification is just a hint that most of the questions are likely to be in that range. In our case, we have all the data ahead of time, so we have no need for the hint.

    Notice that with this change to an owner-data listview, the program starts up almost instantly. Remember also the way we arranged the data in our string pool: All the strings for an item are adjacent, and strings for consecutive items follow one another. This means that all the data for one screenful of information resides in contiguous memory. Result: Better locality, fewer page faults. We'll see more benefits of the string pool later.

    That's all for this month. Next month, we'll come back to filling in the second column of data: the simplified Chinese characters.

  • The Old New Thing

    Displaying the dictionary, part 2: Using text callbacks

    • 12 Comments

    As we noted last time, adding items to the listview takes an absurd amount of time. Today, we'll make a failed attempt at improving this because it lets me illustrate a listview technique and it lays the groundwork for the real fix next time.

    Instead of creating the items in their entirety, let's set their text to LPSTR_TEXTCALLBACK. This is a placeholder value which indicates "I'm not going to tell you what the string is. If you need it, call me back."

    class RootWindow : public Window
    {
     ...
     LRESULT OnCreate();
     LRESULT OnNotify(NMHDR* pnm);
     void OnGetDispInfo(NMLVDISPINFO* pnmv);
     ...
    };
    
    LRESULT RootWindow::OnCreate()
    {
     ...
     // item.pszText = const_cast<LPWSTR>(de.m_pszTrad);
     item.pszText = LPSTR_TEXTCALLBACK;
     ...
       // item.pszText = const_cast<LPWSTR>(de.m_pszPinyin);
       item.pszText = LPSTR_TEXTCALLBACK;
     ...
       // item.pszText = const_cast<LPWSTR>(de.m_pszEnglish);
       item.pszText = LPSTR_TEXTCALLBACK;
     ...
    }
    
    LRESULT RootWindow::OnNotify(NMHDR *pnm)
    {
     switch (pnm->code) {
     case LVN_GETDISPINFO:
      OnGetDispInfo(CONTAINING_RECORD(pnm, NMLVDISPINFO, hdr));
      break;
     }
     return 0;
    }
    
    void RootWindow::OnGetDispInfo(NMLVDISPINFO* pnmv)
    {
     if (pnmv->item.iItem < 0 || // typo fixed 11am
         pnmv->item.iItem >= Length()) {
      return;         // requesting invalid item
     }
    
     if (pnmv->item.mask & LVIF_TEXT) {
      const DictionaryEntry& de = Item(pnmv->item.iItem);
      LPCWSTR pszResult = L"";
      switch (pnmv->item.iSubItem) {
       case COL_TRAD:    pszResult = de.m_pszTrad;    break;
       case COL_PINYIN:  pszResult = de.m_pszPinyin;  break;
       case COL_ENGLISH: pszResult = de.m_pszEnglish; break;
      }
      pnmv->item.pszText = const_cast<LPWSTR>(pszResult);
     }
    
     if (pnmv->item.mask & LVIF_IMAGE) {
      pnmv->item.iImage = -1;
     }
    
     if (pnmv->item.mask & LVIF_STATE) {
         pnmv->item.state = 0;
     }
    
    }
    
    LRESULT RootWindow::HandleMessage(
                              UINT uMsg, WPARAM wParam, LPARAM lParam)
    {
     ...
      case WM_NOTIFY:
       return OnNotify(reinterpret_cast<NMHDR*>(lParam));
     ...
    }
    

    Instead of setting the strings when we create the listview items, we set their texts to LPSTR_TEXTCALLBACK. When the listview needs the text, it sends us a LVN_GETDISPINFO notification, which we handle by returning the data that the listview requested.

    Sidebar: In our case, obtaining the missing data is very fast. If it were slow, we could have optimized the function further by adding the line

     pnmv->item.mask |= LVIF_DI_SETITEM;
    
    to the end. This tells the listview, "Please cache these results and don't ask me for them again." That way, we do the slow computation only once.

    After making these changes (though not the LVIF_DI_SETITEM change; that was just a sidebar), notice that the it didn't really help much. On my machine, the startup time dropped from eleven to ten seconds, but ten seconds is still way too long. This optimization turns out to have been a washout.

    (Note also that our program is now relying heavily on the fact that a vector is a fast random-access data structure.)

    We'll do better next time.

  • The Old New Thing

    Seattle International Juggling Festival 2005

    • 6 Comments

    In Seattle this weekend, you will have the opportunity to see people throwing things more things into the air than they have hands for, and even learn how to do it yourself:

    [T]he primary goal of this festival will be to teach as many people to juggle as possible.

    The Big Show is Saturday at 7pm. The events are free but donations are accepted.

  • The Old New Thing

    Displaying the dictionary, part 1: Naive version

    • 14 Comments

    We return briefly to the ongoing Chinese/English dictionary series and write some code to display all the definitions we had worked so hard to collect. (I figure you're anxious to see something on the screen, so I am going to handle the Traditional Chinese/Simplified Chinese issue later. For now, the "Simplified" column will be blank.)

    Take the dictionary program we've been developing so far and paste it into our new scratch program. (Delete the main function, of course.) First, search/replace and change m_hwndChild to m_hwndLV since our child window is a listview, and it's just nicer to say what it is up front since we're going to be talking about it a lot. Next, make the following additional changes:

    class RootWindow : public Window
    {
    public:
     virtual LPCTSTR ClassName() { return TEXT("Scratch"); }
     static RootWindow *Create();
    protected:
     LRESULT HandleMessage(UINT uMsg, WPARAM wParam, LPARAM lParam);
     LRESULT OnCreate();
     const DictionaryEntry& Item(int i) { return m_dict.Item(i); }
     int Length() { return m_dict.Length(); }
    private:
     enum {
      IDC_LIST = 1,
     };
     enum {
      COL_TRAD,
      COL_SIMP,
      COL_PINYIN,
      COL_ENGLISH,
     };
    private:
     HWND m_hwndLV;
     Dictionary m_dict;
    };
    
    LRESULT RootWindow::OnCreate()
    {
      m_hwndLV = CreateWindow(WC_LISTVIEW, NULL,
                      WS_VISIBLE | WS_CHILD | WS_TABSTOP |
                      LVS_NOSORTHEADER |
                      LVS_SINGLESEL | LVS_REPORT,
                      0, 0, 0, 0,
                      m_hwnd,
                      (HMENU)IDC_LIST,
                      g_hinst,
                      NULL);
    
     if (!m_hwndLV) return -1;
    
     ListView_SetExtendedListViewStyleEx(m_hwndLV,
                                         LVS_EX_FULLROWSELECT,
                                         LVS_EX_FULLROWSELECT);
    
     LVCOLUMN lvc;
    
     lvc.mask = LVCF_TEXT | LVCF_WIDTH;
     lvc.cx = 200;
     lvc.pszText = TEXT("Traditional");
     ListView_InsertColumn(m_hwndLV, COL_TRAD, &lvc);
    
     lvc.mask = LVCF_TEXT | LVCF_WIDTH;
     lvc.cx = 200;
     lvc.pszText = TEXT("Simplified");
     ListView_InsertColumn(m_hwndLV, COL_SIMP, &lvc);
    
     lvc.mask = LVCF_TEXT | LVCF_WIDTH;
     lvc.cx = 200;
     lvc.pszText = TEXT("PinYin");
     ListView_InsertColumn(m_hwndLV, COL_PINYIN, &lvc);
    
     lvc.mask = LVCF_TEXT | LVCF_WIDTH;
     lvc.cx = 800;
     lvc.pszText = TEXT("English");
     ListView_InsertColumn(m_hwndLV, COL_ENGLISH, &lvc);
    
     ListView_SetItemCount(m_hwndLV, Length());
    
     for (int i = 0; i < Length(); i++) {
      const DictionaryEntry& de = Item(i);
      LVITEM item;
      item.mask = LVIF_TEXT;
      item.iItem = i;
      item.iSubItem = COL_TRAD;
      item.pszText = const_cast<LPWSTR>(de.m_pszTrad);
      item.iItem = ListView_InsertItem(m_hwndLV, &item);
      if (item.iItem >= 0) {
       item.iSubItem = COL_PINYIN;
       item.pszText = const_cast<LPWSTR>(de.m_pszPinyin);
       ListView_SetItem(m_hwndLV, &item);
       item.iSubItem = COL_ENGLISH;
       item.pszText = const_cast<LPWSTR>(de.m_pszEnglish);
       ListView_SetItem(m_hwndLV, &item);
      }
     }
     return 0;
    }
    

    After creating the listview control, we set it into full row select mode and create our columns. Before inserting the words into the dictionary, we use ListView_SetItemCount to tell the listview the number of items we're about to put into the listview. (This is optional; it allows the listview to pre-allocate some structures.) I'm not using an STL iterator because this code is going to be deleted soon. You'll find out why if you can't figured it out already.

    Compile and run this program. Notice that it takes a ridiculously long time to start up. That's because our loop is inserting 20,000 dictionary entries into the listview, and that can't be fast.

    Next time, we'll work on speeding that up.

  • The Old New Thing

    Maintaining high standards at the International Frederic Chopin Piano Competition

    • 12 Comments

    The quintennial International Frederick Chopin Piano Competition will be held later this year, and I was reminded that the awards for "Best performance of a mazurka" and "Best performance of a concerto" have not been awarded since 1985. Simply put: Nobody since 1985 has been good enough to deserve it.

    The year 1995 was a particularly bad year for Chopin-lovers. The judges for Competition XIII concluded that none of the 130 entrants deserved any of the four big-name prizes.

    • First prize - not awarded.
    • Best perfomance of the mazurkas - not awarded.
    • Best performance of a polonaise - not awarded.
    • Best performance of a concerto - not awarded.

    (This wasn't the first time the judges refused to award first prize. It happened five years earlier as well.)

  • The Old New Thing

    Why does Explorer eject the CD after you finish burning it?

    • 44 Comments

    Partly as a convenience, but partly to work around buggy hardware. The developer responsible for CD burning explained it to me.

    Most CD drives cache information about the disc in their internal memory to improve performance. However, some drives have a bug where they fail to update the cache after the CD has been written to. As a result, you can write some data to a CD, then ask the CD drive for the data you just wrote, and it won't be there! The drive is returning the old cached data instead of the new data. For most drives, ejecting and reinserting the CD is enough to force the drive to update its internal cache.

    "But wait, it gets worse!" I'm told.

    Some drives are "smart" and realize you've reinserted the same media, and then don't update. These drives require that you put in another type of media (or pressed CD-ROM media) to force them to update. These drives were manufactured around 2002, and new drives don't have it this bad, but still have the above problem requiring an eject/insertion cycle.

    So there's your tip for the day. If you are burning data to a CD and you find the data isn't there, try ejecting the disc and reinserting it. If your drive is particularly buggy, you'll have to eject the disc, insert a different type of disc, then eject that second disc and reinsert the first one.

  • The Old New Thing

    Why can't the default drag/drop behavior be changed?

    • 44 Comments

    A common reaction to my explanation of whether dragging a file will result in a move or copy was that there should be a setting that lets you change the algorithm by which Explorer decides whether you want to move or copy.

    There are a few reasons why this is a bad idea.

    First, if there were such a setting, then it removes some of the predictability from the user interface. One of the benefits of a common user interface is that once you learn it, you can apply the rules generally. But if each user could customize how drag/drop works, then the knowledge you developed with drag/drop wouldn't transfer to other people's machines.

    Some people view infinite customizability as a good thing. But each added bit of customizability increases the possibility that a particular combination of settings won't get tested as heavily as perhaps it should. ("What do you mean, this doesn't work if you have the notification icons set to hide after only 5 seconds, the taskbar's auto-hide delay customized to a value larger than 5 seconds, the taskbar buttons customized to a boldface font larger than 14pt, and drag/drop operations defaulting always to move? How could you have missed that combination in your testing? Surely you should have anticipated the interaction between an auto-hide delay longer than the notification auto-hide delay combined with a nondefault drag on a network with fewer than 50 machines!")

    Infinite customizability also means that you can't just sit down in front of somebody's machine and start using it. You first have to learn how they customized their menus, button clicks, default drag effects, and keyboard macros. "Oh, on this machine, you paste by shift-right-clicking. Sorry. On my machine, I use ctrl-alt-middle-click to paste." Imagine if everybody could easily customize the order of the clutch, brake, and gas pedals in their car to suit their fancy.

    There is also the branding element. Like the Mac, Windows tries to cultivate a specific "look" that makes people say, "Hey, this computer is running Windows; I know how to use it!" My DVD player and my car both show the manufacturer's logo when they are booting up. So too does Windows.

    Even if the "change the default drag/drop behavior" option passed "settings court" and was deemed worth the additional test cost, you still have the problem that it affects only Explorer. Other programs would continue to use the old algorithm, at least until you found their settings to change how they perform default drag/drop as well, if such a setting existed at all. Imagine the confusion if Windows Explorer followed one set of rules, but Microsoft Outlook followed a different set of rules. "Oh right, this is a mail message I'm dragging; the default operation is going to be a move, not a copy."

  • The Old New Thing

    Can you trust the Man on the Street interview?

    • 13 Comments

    Occasionally, in a news story, the reporter will ask for comments or opinion from a passer-by (nicknamed "the man on the street"). Greg Packer has created a second career as that man.

    In the last 10 years, he's been quoted at least a dozen times by the New York Post. He's been quoted at least 14 times by the Daily News, most recently just last week. He was quoted in the Atlanta Journal-Constitution two weeks ago. And Packer has been quoted or photographed at least 16 times on separate occasions by the Associated Press. ...

    [H]e checks the newspapers for concerts, sports games, parades, book signings - anywhere media trucks might be camped out. Then, he requests time off from his job as a highway worker on Long Island and shows up early, scanning the crowd for reporters.

    It got so bad that the Associated Press issued an internal memo instructing reporters not to talk to the guy any more!

    That story from On the Media reminded me of a related incident back when the hype surrounding Star Wars: The Phantom Menace was building. The New York Times sent a reporter to cover the people who had been waiting in line for months. The first person interviewed is Sangay Kumar, who claims to have flown in from Bombay just to see the movie.

    A friend of mine read the article and started laughing.

    Because my friend knows Mr. Kumar, who it turns out is not actually from Bombay. He's from Baltimore. He was just waiting in line with everybody else and saw a reporter coming and decided to put on a campy Indian accent and make up a nutty story. And the reporter bought it.

  • The Old New Thing

    Why don't control panel programs and property sheets show up in the taskbar?

    • 50 Comments

    Control panel programs and property sheets don't show up in the taskbar. Why not?

    As I recall, the explanation was that control panel programs and property sheets aren't applications. They are auxiliary helper windows that assist you with a task, but they aren't a program in their own right. Therefore, they don't get a taskbar button.

    I've always been kind of suspicious of that explanation, but there it is, make of it what you will. (I don't mind the behavior—putting them in the taskbar just creates clutter—but the explanation I found kind of wanting.)

  • The Old New Thing

    Answer to quick puzzle about security and synchronization

    • 5 Comments

    As many people quickly figured out, the reason why the the WaitForSingleObject returns immediately is that the call is failing. The reason is that the second process opened the handle with EVENT_MODIFY_STATE access, which grants permission to call the SetEvent function, the ResetEvent function, and the fatally flawed PulseEvent function, but it doesn't include SYNCHRONIZE access, which is necessary if you intend to synchronize on the object (i.e., wait on it).

    The fix is for Process B to ask for SYNCHRONIZE access instead of EVENT_MODIFY_STATE.

    The fact that it's happening in a second process is a red herring. You can put this code in the same process and it will fail/succeed in the same way:

    HANDLE hEventA = CreateEvent(NULL, FALSE, TRUE, TEXT("MyNamedEvent"));
    HANDLE hEventB = OpenEvent(EVENT_MODIFY_STATE, FALSE, TEXT("MyNamedEvent"));
    WaitForSingleObject(hEventB, INFINITE); // fails
    

    Indeed, the fact that the object is named is a red herring. It has nothing to do with named/unnamed objects.

    HANDLE hEventA = CreateEvent(NULL, FALSE, TRUE, NULL);
    HANDLE hEventB;
    DuplicateHandle(GetCurrentProcess(), hEventA,
                    GetCurrentProcess(), &hEventB,
                    EVENT_MODIFY_STATE, FALSE, 0);
    WaitForSingleObject(hEventB, INFINITE); // fails
    

    In all three cases, the fix is to change EVENT_MODIFY_STATE to SYNCHRONIZE.

Page 362 of 439 (4,383 items) «360361362363364»