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


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.

Comments (26)
  1. Anonymous says:

    there’s no doubt that ownerdata is making things faster but don’t you think that calling SetItemCount(20000) to boot would have had a significant impact (improvement) on yesterday’s callback approach too?

  2. Um, the call to SetItemCount came from yesterday’s program in the first place.

  3. Anonymous says:

    right, this will be the program of the day before yesterday then :)

    still yesterday you reported startup times of 10 seconds for 20000 items whereas I have timing data for 7000 items added in under 1 second — and that’s listview adding combined with some shell calls to read folder contents.

    the scale-up 7000->20000 won’t be exactly linear but still i can’t see how under 1 sec can become 10! Have you been using your antique laptop again? :)

    or it’s all (most) down to these strings and containers you use, not the listview itself

  4. Anonymous says:

    Hi Raymond, this is a totally unrelated subject, but I thought you could help me out.

    I lost the Admin password on a WindowsNT machine. Apart from a format hard drive, is there any other way I can reset the password?

    The machine also has Win 95 and it boots up just fine.

    Thanks in advance,

    Eldo

  5. binaryc says:

    I don’t know if Raymond can help you, but google sure can.

    http://www.google.com/search?lr=&ie=UTF-8&oe=UTF-8&q=I%20lost%20the%20Admin%20password%20on%20a%20WindowsNT%20machine.

    Seriously, before you ask a question, just type the exact question in google and see what happens.

  6. Mike Dimmick says:

    Eido: ERD Commander from Winternals Software should sort you out. http://www.winternals.com/Products/ErdCommander/

    Price is $149 for the workstation version and $299 for the server edition.

  7. Um the call to SetItemCount existed in the program the day before yesterday too. Could you at least check before asking questions?

  8. PatriotB says:

    I was right! I figured you would go for an owner-data listview, a.k.a. virtual listview, to speed it up.

  9. Anonymous says:

    you are reading my response the wrong way!

    i did see the SetItemCount call in the other day’s program and i admitted my blunder

    however my personal timing experiences wrt adding loads of items to listviews do not reproduce your findings, as i mentioned in my previous post

  10. Sorry, I misunderstood what you meant by "this will be the program of the day before yesterday then". I thought you mean "Please apply my remarks to the program of the day before yesterday."

    Your performance will differ from mine because your computer is probably a lot faster than mine.

  11. Anonymous says:

    Quick question about this:

    Exercise: Why is HEADER a union containing a structure rather than just being a structure? What is the significance of the alignment member?

    I think the purpose is so that the HEADER is at least the size of a WCHAR so that the block of memory after the header is suitably aligned for use as a WCHAR, right?

    But for this to work, the size of the struct inside the HEADER should be <= the sizeof the WCHAR, or we’d have to change the alignment member to an array of two or more WCHARs?

  12. Anonymous says:

    The union like that makes sure the header has at least the same alignment/size of a WCHAR. A much better way would have been to use a flexible array member like: struct HEADER { HEADER *next; SIZE_T size; WCHAR buf[] }; then he could of gotten rid of most of the casting. But it’s not in standard C++ yet.

  13. Anonymous says:

    commenting on nikos’ comment about speed differences, one of the more siginificant reasons for me not to upgrade my development computer (money is not an issue) is that buying a fast machine will tend to mask task durations that on slower machines might seem unacceptable. so i keep my 1.1MHz Duron and try to improve my algorithmns, knowing that on any machine faster than mine the results will be positive.

  14. Anonymous says:

    <s>algorithmns</s> algorithms

  15. Anonymous says:

    This is another reason for dual machine development on windows – your IDE runs on the fastest thing you can afford and you run your app on another machine, preferably something near your target minimum speed.

    Remote debugging has been really good for me since VC6, I never used it before then, but I find the screen real-estate invaluable when the debugger is running. Plus, if you’re going to mess about with full screen DX then it’s pretty much essential.

  16. Anonymous says:

    I am seeing little squares in place of the traditional characters when I run this. I see the pinyin and english fine. Anyone know what I’m missing?

    I’m running Windows 2000. I can see the traditional characters when I drag and drop the cedict.b5 file onto internet explorer.

  17. Anonymous says:

    Will your dictionary conveniently forget words like ‘democracy’, ‘freedom’ and ‘demonstration’? Microsoft seems to think that this is the right thing to do.

  18. Anonymous says:

    does the guy who converted the first article in c# still doing it?

    what was the blog adress?

  19. Anonymous says:

    grolou: Rico Mariani writes the C# blog that (I believe) you are refering to. Its at http://blogs.msdn.com/ricom/ , but he hasn’t written anything regarding this topic.

  20. Anonymous says:

    "That’s all for this month."

    All on this program, or all for the journal…?

    (Hopefully not the latter – what else would we read for the next couple of weeks!)

  21. Anonymous says:

    dan.g: how about algorythms?

    da da da

    :-)

  22. Anonymous says:

    Wednesday, June 15, 2005 9:04 PM by outraged

    > Will your dictionary conveniently forget

    > words like ‘democracy’, ‘freedom’

    > and ‘demonstration’? Microsoft seems to

    > think that this is the right thing to do.

    1. Only from the version with simplified Chinese characters.

    2. Of course not, Mr. Chen knows not to give in to such outrages. But Microsoft will delete his blog after that, because Microsoft thinks that this is the right thing to do.

    By the way despite my opinion of Microsoft I do value most of the contents of these blogs. I wish there were some other solution. Like maybe, Microsoft would stop censoring and China would kick all of Microsoft out of China. (Meanwhile of course China needs to kick Red Flag Linux out of China because of Linux’s free roots.)

  23. Anonymous says:

    @Norman Diamond and the troll:

    Ethics are important, but this is a technical post on a technical blog and this really doesn’t seem to be the right place to debate ethical issues and increase the noise.

    What Microsoft does in China is irrelevant when you’re trying to build a dictionary.

  24. Anonymous says:

    Hopefully rico will do a C# version. A simple java version i threw together starts up in under a second.

    The standard way to do tables in java is to use TableModels which basically do the same thing as owner-data. I assume it is the same in C#.

    And the nice thing is to get Chinese characters you just need to set a font which can display them.

  25. Anonymous says:

    MB wrote:

    > I am seeing little squares in place

    > of the traditional characters when I

    > run this. I see the pinyin and english

    > fine. Anyone know what I’m missing?

    That’s because your system doesn’t have Chinese support installed. You can go to Control Panel -> Regional Options and add there Chinese language support. It will add Chinese script to most of fonts.

    Alternatively, you can explicitly set Unicode font to List-View control. I believe "Arial Unicode MS" came with MS Office. So, in RootWindow::OnCreate function just after List-View is created I create the font and set it to the control:

    LOGFONT lf = { 0 };

    GetObject(GetStockObject(DEFAULT_GUI_FONT), sizeof(LOGFONT), &lf);

    lstrcpy(lf.lfFaceName, TEXT("Arial Unicode MS"));

    m_hfont = CreateFontIndirect(&lf);

    SetWindowFont(m_hwndLV, m_hfont, FALSE);

    On WM_NCDESTROY I delete the font:

    case WM_NCDESTROY:

    DeleteFont(m_hfont);

Comments are closed.