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

Date:June 15, 2005 / year-entry #152
Tags:code
Orig Link:https://blogs.msdn.microsoft.com/oldnewthing/20050615-30/?p=35313
Comments:    26
Summary: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...

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. nikos says:
    June 15, 2005 at 9:43 am

    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. Raymond Chen - MSFT says:
    June 15, 2005 at 10:05 am

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

  3. nikos says:
    June 15, 2005 at 10:17 am

    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. Eldo says:
    June 15, 2005 at 10:30 am

    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:
    June 15, 2005 at 10:38 am

    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:
    June 15, 2005 at 10:40 am

    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. Raymond Chen - MSFT says:
    June 15, 2005 at 11:05 am

    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:
    June 15, 2005 at 11:34 am

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

  9. nikos says:
    June 15, 2005 at 11:55 am

    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. Raymond Chen - MSFT says:
    June 15, 2005 at 12:02 pm

    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. sriram says:
    June 15, 2005 at 1:03 pm

    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. asdf says:
    June 15, 2005 at 7:28 pm

    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. .dan.g. says:
    June 15, 2005 at 7:47 pm

    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. .dan.g. says:
    June 15, 2005 at 7:49 pm

    <s>algorithmns</s> algorithms

  15. Chris Redpath says:
    June 15, 2005 at 8:01 pm

    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. MB says:
    June 15, 2005 at 8:19 pm

    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. outraged says:
    June 15, 2005 at 9:04 pm

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

  18. grolou says:
    June 15, 2005 at 11:54 pm

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

    what was the blog adress?

  19. kpp says:
    June 16, 2005 at 12:29 am

    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. Paul says:
    June 16, 2005 at 8:12 am

    "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. Dan McCarty says:
    June 16, 2005 at 1:02 pm

    dan.g: how about algorythms?

    da da da

    :-)

  22. Norman Diamond says:
    June 16, 2005 at 7:45 pm

    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. James Griffin says:
    June 16, 2005 at 8:52 pm

    @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. Asd says:
    June 17, 2005 at 6:54 am

    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. Alex Blekhman says:
    June 20, 2005 at 3:46 am

    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);

  26. smallcode»Blog Archive » An approach to API calls optimization says:
    August 14, 2006 at 9:00 pm

    PingBack from http://smallcode.weblogs.us/2006/08/15/an-approach-to-api-calls-optimization/

Comments are closed.


*DISCLAIMER: I DO NOT OWN THIS CONTENT. If you are the owner and would like it removed, please contact me. The content herein is an archived reproduction of entries from Raymond Chen's "Old New Thing" Blog (most recent link is here). It may have slight formatting modifications for consistency and to improve readability.

WHY DID I DUPLICATE THIS CONTENT HERE? Let me first say this site has never had anything to sell and has never shown ads of any kind. I have nothing monetarily to gain by duplicating content here. Because I had made my own local copy of this content throughout the years, for ease of using tools like grep, I decided to put it online after I discovered some of the original content previously and publicly available, had disappeared approximately early to mid 2019. At the same time, I present the content in an easily accessible theme-agnostic way.

The information provided by Raymond's blog is, for all practical purposes, more authoritative on Windows Development than Microsoft's own MSDN documentation and should be considered supplemental reading to that documentation. The wealth of missing details provided by this blog that Microsoft could not or did not document about Windows over the years is vital enough, many would agree an online "backup" of these details is a necessary endeavor. Specifics include:

<-- Back to Old New Thing Archive Index