How about this: allocate some relatively small memory space for each item (say 4kb), so you will have room for small and fast modifications without changing the pointer. That way you can use the GETDISPINFO trick, giving it a pointer and telling listview not to retrieve it again. If you need more room, you can realloc the memory and tell listview to invalidate data for that item (causing the LVN_GETDISPINFO message to arrive again). That way memory usage will be higher, but you have a fast and easy way of changing your items data.


I had thought of the static memory locations, but at the end, unallocating the lot would be evil (the main problem with the listviews, the destroying of them is relatively fast until I destroy the main window on close, then the whole thing sits there for a few minutes). I'm really beginning to think I have to manually make my own control from scratch. As the GETDISPINFO actually will reoccur if you roll the mouse over the listview (to get any tooltip info, if any). I'm still not convinced going to a control is going to get any faster, just wish I could find a RichEdit that offered more than 65535 lines with access to them, as that code worked reasonably well (until I hit 65535 lines and it all went south). I had thought of going the route of multiple RichEdit controls, but then I'd still have to parallel the ListViews to keep up, which would be insane on GDI usage.



BTW, the dispinfo message should be replied always if you do this... disregarding the message when the item is invisible will only cause listview to resend the message several times. Anyway, I think (but I have not confirmed this) that message is only sent when the items data is updated, for newly added items, and when an item becomes visible. So in most cases you could rely on listview not asking for the data too often.


Actually, as I said up there, if you move the mouse over listitems, it asks for dispinfo again, to see if there's any tooltip for the entry. I watched it happen a lot. Just wish I knew what all those other messages were, since I couldn't find references to them.



Yes, it didn't seem much of an idea... it could be useful, though, if you become severely limited my memory usage, and need to sacrifice some speed to make the program work with very large lists. After all, a slow program is better than a crashed one :grin:


I'm wondering if there area any good references to database work, so I can actually see if there's anything there I can use, as this is driving me nuts. I still need to keep the data in text format for flippin' sake. :(
Posted on 2003-08-10 10:42:24 by FunkyMeister
I've been trying to implement my suggestions in my last post, I made a little test program, and it has exactly the problems you pointed out. Reusing pointers is still a good idea (less memory reallocations => less fragmentation), but the listview itself is very slow when handling too many items, no matter how you store the labels.

But how about this: keep ALL of your item data in your favorite structure (b-trees, linked list, whatever), and in the list view you only instert those items you want to show. The trick is then you subclass the listview, and handle the scroll events yourself. Instead of scrolling, you change the items text (the dummy ones in the control, I mean). That way you would not depend on listview's way of storing it's data.

I also thought of a cosmetic feature: when you are about to close the listview's parent, first show a popup like "Please wait, releasing database" or some stuff like that, then send LVM_DELETEALLITEMS, and then close.

Also, if you are handling LVN_DELETEITEM, you could have a global variable acting as a flag, when it's set you don't process that message. That way if you are releasing all of your data, you can do it massively later, instead of freeing the memory belonging to each item.
Posted on 2003-08-11 15:39:05 by QvasiModo

I've been trying to implement my suggestions in my last post, I made a little test program, and it has exactly the problems you pointed out.

Which ones did you hit exactly? I may be able to help out with that. :)

Reusing pointers is still a good idea (less memory reallocations => less fragmentation), but the listview itself is very slow when handling too many items, no matter how you store the labels.

I'm noticing that with a lot of controls, though if I had a means of using some means of a storage area (I was using the RichEdit control, as it had the large storage capacity with fast load/save and release, but the 16 bit line location limitation was horrible, I was in the middle of writing a new one when I shelved the idea for another possibility, got that far and found the listviews stunk the high heaven when things get too large). If I do that, I'll most likely just make a fake control and toss a scroll bar to read for offset, then draw the info myself into an empty area. It'll take a lot of work to do that though, as I did get the line counting routine done, but not the stream part of it (did it internally on a short 100k string, worked flawlessly). It's going to take a ton of work to do all that.

But how about this: keep ALL of your item data in your favorite structure (b-trees, linked list, whatever), and in the list view you only instert those items you want to show. The trick is then you subclass the listview, and handle the scroll events yourself. Instead of scrolling, you change the items text (the dummy ones in the control, I mean). That way you would not depend on listview's way of storing it's data.

I'd thought of that above, but it's finding a control that I can be lazy with, or a database where I can work with text based data (which isn't CSV'ed), it's going to take some planning apparently.

I also thought of a cosmetic feature: when you are about to close the listview's parent, first show a popup like "Please wait, releasing database" or some stuff like that, then send LVM_DELETEALLITEMS, and then close.

Actually, I got lazy, the status bar just says "Shutting Down..." :grin:

Also, if you are handling LVN_DELETEITEM, you could have a global variable acting as a flag, when it's set you don't process that message. That way if you are releasing all of your data, you can do it massively later, instead of freeing the memory belonging to each item.

Hmmm, that's interesting, you mean when I destroy the object, it goes through the entire list deleting items?! (The oddity is the last list takes ages to destroy, the first few take less, and can have as much as the first in them.) I'd rather release it in one fast shot. (About as fast as it does when I screw up and GPF the sucker.) :grin:
Posted on 2003-08-11 16:30:48 by FunkyMeister

Which ones did you hit exactly? I may be able to help out with that. :)

I'm attaching my source, along with some earlier experiments... have fun :grin:
Hmmm, that's interesting, you mean when I destroy the object, it goes through the entire list deleting items?! (The oddity is the last list takes ages to destroy, the first few take less, and can have as much as the first in them.) I'd rather release it in one fast shot. (About as fast as it does when I screw up and GPF the sucker.) :grin:

Well, I was storing a memory object for each item, and deleting them when I received LVN_DELETEITEM. When the control closes, it actually deletes the items one by one, apparently this is necessary since there is no notification message to delete all items (the LVN_DELETEALLITEMS is sent only after they were deleted, it indicated that the list is now empty). So when I destroy the control, I can't process LVN_DELETEITEM messages, or it takes ages... :mad:

On a different topic, I still can't get the treeview to stop that bizarre doubleclick behavior... so if you still have that source you mentioned some posts earlier, let's have a look at it... :)
Posted on 2003-08-12 10:28:38 by QvasiModo


I'm attaching my source, along with some earlier experiments... have fun :grin:

The list took forver to populate. (Because it was drawing the changes.) I know it's sane not to do that. :) Tinkering to solve my problems were you? :grin:


Well, I was storing a memory object for each item, and deleting them when I received LVN_DELETEITEM. When the control closes, it actually deletes the items one by one, apparently this is necessary since there is no notification message to delete all items (the LVN_DELETEALLITEMS is sent only after they were deleted, it indicated that the list is now empty). So when I destroy the control, I can't process LVN_DELETEITEM messages, or it takes ages... :mad:

I'm wondering, what is the order, does WM_DESTROY come into play first? Or does it just go through all the LVN_DELETEITEMs and then LVN_DELETEALLITEMS and then finally WM_DESTROY, I somehow think WM_DESTROY gets there first. I presume I could easily unlump the entire mass of memory in one shot, ignore the LVN_DELETEITEMs when I know they're gone. I'm trying to figure out where the LVN_DELETEITEMs is coming from, most likely the view, but the WM_DESTROY caused it, hmm, maybe make the mass delete at the WM_DESTROY, zero the count of listitems and let the rest do it's normalcy. That way the data can be in larger memory chunks. It's still a mess to design, because I need to do this with text based data on the 10+megabyte range (and a lot higher). :( We're talking 100's of thousands of lines. And it's got to be lightning fast or it'll cause system performance loss. :( (It's doing that now with it's current mayhem.)


On a different topic, I still can't get the treeview to stop that bizarre doubleclick behavior... so if you still have that source you mentioned some posts earlier, let's have a look at it... :)

On the treeview, on the message TVM_HITTEST
Cheat and call the original WindProc (with all the params, let the message go through first on this, it's sneaky doing this, but it works) to do the normal hittest, then when it's done, it'll update the lParam's TVHITTESTINFO structure. The hItem in that, is the item the mouse is over. The Flags will contain all the flags that define where the mouse is and need to be ANDed against the TVHT_... values, so you can tell where the mouse IS over the item. :) That includes the checkbox.

I have to dig through my code to find it. :) (Yep, there's a lot of it.) The references I found were from MSDN about doing this, it basically lets me find out where the mouse is when a hit test comes in (which is whenever you move the mouse when it's over the view, and that means every time).

What I was suggestioning, was to store the hItem that you're over, into a local variable only IF you're on the actual label, if not zero the local variable, when a doubleclick comes in, if the local variable is 0, ignore it, but say you processed it AND don't let the original WindProc run.
Posted on 2003-08-12 11:40:10 by FunkyMeister


The list took forver to populate. (Because it was drawing the changes.) I know it's sane not to do that. :) Tinkering to solve my problems were you? :grin:

:grin: :grin: :grin:
Actually I don't try to redraw, but listview does that by itself :mad: so I made my test app a multithreaded one. The worker thread adds the items, and the GUI thread handles the messages. My next try willl be different, I will try to handle all of the storage myself, so I don't have to call LVM_INSERTITEM, instead I can populate the list in one shot.

BTW, in case you haven't toyed much with the little demo, I tell you that clicking in the column headers sorts the list (but DON'T try it, unless you want to know the real meaning of the word "slow" :grin: ,). Also hitting DEL deletes the selected items, and F2 allows you to edit the item's labels.

I'm wondering, what is the order, does WM_DESTROY come into play first? Or does it just go through all the LVN_DELETEITEMs and then LVN_DELETEALLITEMS and then finally WM_DESTROY, I somehow think WM_DESTROY gets there first. I presume I could easily unlump the entire mass of memory in one shot, ignore the LVN_DELETEITEMs when I know they're gone. I'm trying to figure out where the LVN_DELETEITEMs is coming from, most likely the view, but the WM_DESTROY caused it, hmm, maybe make the mass delete at the WM_DESTROY, zero the count of listitems and let the rest do it's normalcy. That way the data can be in larger memory chunks. It's still a mess to design, because I need to do this with text based data on the 10+megabyte range (and a lot higher). :( We're talking 100's of thousands of lines. And it's got to be lightning fast or it'll cause system performance loss. :( (It's doing that now with it's current mayhem.)

This is what happens:
1. System sends WM_DESTROY to control.
2. Control sends WM_NOTIFY -> LVN_DELETEITEM for each item as they are deleted.
3. Control sends WM_NOTIFY -> LVN_DELETEALLITEMS once, when the list is cleared.
3. Control is destroyed.

So if you were freeing the memory as the items were deleted, you should take this listview's behavior in consideration. Deleting too many items one by one is MUCH slower than deleting the whole thing (try it with the demo... instead of closing the app, select all the items and hit DEL... and prepare to ait a looong time :grin: )

There's one thing I don't undestand, though. Is it really necessary to show all this info at once? I'm assuming here that the operations on the data do not depend on user input, maybe you are mantaining a database, or reading data from a device, a network or an external app. That's nother reason of why my demo uses to threads... originally I intended to make to worker thread sort, add and delete items randomly, to simulate those conditions you described some posts ago.

As for the treeview mess, I'll try your suggestions as soon as I find the time for it... I've made some other small fixes, but I'm waiting to solve this one before positng the new version.
Posted on 2003-08-12 16:22:48 by QvasiModo


:grin: :grin: :grin:
Actually I don't try to redraw, but listview does that by itself :mad: so I made my test app a multithreaded one. The worker thread adds the items, and the GUI thread handles the messages. My next try willl be different, I will try to handle all of the storage myself, so I don't have to call LVM_INSERTITEM, instead I can populate the list in one shot.

BTW, in case you haven't toyed much with the little demo, I tell you that clicking in the column headers sorts the list (but DON'T try it, unless you want to know the real meaning of the word "slow" :grin: ,). Also hitting DEL deletes the selected items, and F2 allows you to edit the item's labels.

Yes, the listview is annoying, but I usually lock the window before I work on it, then it doesn't redraw stupidly after each insert. Although, I was working on a means of setting a "fake" redraw disable, but didn't seem to get far with all the messages I had to watch.

Ad yes, saw the DEL and F2 key sfor editing. As for deleting those entries, yes, I'm well aware of how LOOOONG it takes. :D I'm just wishing I could find a means to do this amount of data without the hassles. I guess writing a new control is going to be it, or mangling a new one out of the use of another.


This is what happens:
1. System sends WM_DESTROY to control.
2. Control sends WM_NOTIFY -> LVN_DELETEITEM for each item as they are deleted.
3. Control sends WM_NOTIFY -> LVN_DELETEALLITEMS once, when the list is cleared.
3. Control is destroyed.

So if you were freeing the memory as the items were deleted, you should take this listview's behavior in consideration. Deleting too many items one by one is MUCH slower than deleting the whole thing (try it with the demo... instead of closing the app, select all the items and hit DEL... and prepare to ait a looong time :grin: )

I thought of possibly intercepting the WM_DESTROY and using a memory pool method to unallocate the lot faster, but that'll involve more memory to keep track of all the allocs. A second list. Though, finding data in it would be blindingly fast, until it was sorted. :(


There's one thing I don't undestand, though. Is it really necessary to show all this info at once? I'm assuming here that the operations on the data do not depend on user input, maybe you are mantaining a database, or reading data from a device, a network or an external app. That's nother reason of why my demo uses to threads... originally I intended to make to worker thread sort, add and delete items randomly, to simulate those conditions you described some posts ago.

Actually, the datat itself is worked on before this list opens, but the user interaction is necessary to pick/choose items out of the list to either delete, move, swap out of the list to another list (on disk) and finally to assemble into a smaller data chunk of a special kind.


As for the treeview mess, I'll try your suggestions as soon as I find the time for it... I've made some other small fixes, but I'm waiting to solve this one before positng the new version.

It should help, I'm still not finding that code (probably burried it somewhere on a RW someplace, if thats the case, could take weeks to find, hey never said I was organized).
Posted on 2003-08-13 15:13:03 by FunkyMeister

Yes, the listview is annoying, but I usually lock the window before I work on it, then it doesn't redraw stupidly after each insert. Although, I was working on a means of setting a "fake" redraw disable, but didn't seem to get far with all the messages I had to watch.

Good idea... I didn't think of locking...
I thought of possibly intercepting the WM_DESTROY and using a memory pool method to unallocate the lot faster, but that'll involve more memory to keep track of all the allocs. A second list. Though, finding data in it would be blindingly fast, until it was sorted. :(

I was allocating everything in a memory heap, so freeing the whole lot was just as simple as destroying the heap. No need to keep track of all the allocs. However, heaps are very slow... perhaps the solution would be to implement your own heap (with all the extra work that implies :( )

Unfortunately, I couldn't find the time for this since I'm back to college now, maybe next weekend I'll try the tweaking a listview to store all the item's data myself and see if it's really faster. But I still think that the main bottleneck is in the data structures used to store 13 megs of data in RAM... and I'm not very good on b-trees, search algos, etc yet. I never had an allocation problem that required something more complicated than a linked list before, and I hae the feeling that's not going to help much here :( .
It should help, I'm still not finding that code (probably burried it somewhere on a RW someplace, if thats the case, could take weeks to find, hey never said I was organized).

Sounds familiar :grin: :grin:
Anyway, I just need to know how to prevent treeview from catching on when a doubleclick event happened... blocking the WM_DBLCLK message does not seem to work. You mentioned something about changing the mouse state, but I don't know how to do that. The problem is I'm not sure of how you solved this problem before, I think with a little more info I'll get it right. :)
Posted on 2003-08-19 13:03:13 by QvasiModo
Originally posted by QvasiModo
Good idea... I didn't think of locking...

I figured it was faster than dealing with the refresh consistantly.
Originally posted by QvasiModo
I was allocating everything in a memory heap, so freeing the whole lot was just as simple as destroying the heap. No need to keep track of all the allocs. However, heaps are very slow... perhaps the solution would be to implement your own heap (with all the extra work that implies :( )

I think a linked list would require a lot of work, but would do a somewhat efficient trick if I prealloc'ed the entire mess in larger blocks (but that presents a memory constraint issue).
Originally posted by QvasiModo
Unfortunately, I couldn't find the time for this since I'm back to college now, maybe next weekend I'll try the tweaking a listview to store all the item's data myself and see if it's really faster. But I still think that the main bottleneck is in the data structures used to store 13 megs of data in RAM... and I'm not very good on b-trees, search algos, etc yet. I never had an allocation problem that required something more complicated than a linked list before, and I hae the feeling that's not going to help much here :( .

Ah, thoe days long behind me. (I'll get my cane out... ) Yes, doing a linked list was my first thought, but as I said above, it'll hog memory. Or chop the crap out of it even worse.
Originally posted by QvasiModo
Sounds familiar :grin: :grin:
Anyway, I just need to know how to prevent treeview from catching on when a doubleclick event happened... blocking the WM_DBLCLK message does not seem to work. You mentioned something about changing the mouse state, but I don't know how to do that. The problem is I'm not sure of how you solved this problem before, I think with a little more info I'll get it right. :)

Try a parent window (create a dummy window), set the list so it's owner done (too tired at the moment to remember the right tag), the parent window should receive the proper mouse events, if not, I recall the mouse UP event happened on a double click.
Posted on 2003-08-19 21:42:01 by FunkyMeister

Ah, thoe days long behind me. (I'll get my cane out... )

:grin: :grin: :grin:
Try a parent window (create a dummy window), set the list so it's owner done (too tired at the moment to remember the right tag), the parent window should receive the proper mouse events, if not, I recall the mouse UP event happened on a double click.

Not sure I got the point of the dummy window... :(
Will try debugging the program to see exactly what messages are being send on a double click event, perhaps my last attempt didn-t work because I overlooked some message.

On the listview issue, did you take a look at this thread ?
Posted on 2003-08-20 16:47:46 by QvasiModo
hi,
i am in the same situation where i switched to OnwerData ListView (Virtual Listview).
sadly enough i must handle more than 1,000,000 items ..
that aint problem since v_listview can handle that, but indeed the memory is a problem..
for 300,000 items my app's process mem usage takes about 30mb +- with no PF.
this i do using the STL lib (as i do C coding as well), but as for non HL i guess 1 sullotion would be to store the data in the HHD and access it from the GETDISPINFO.. it is slow, but much safer than mem.
if we choose file, it would be best to use db file and using a key to our data for each item.
i can process 1,000,000 items per sec (did a test) and will take 50++MB :( i guess there isn't much of a choise here > file :( ?
Posted on 2003-08-20 17:52:05 by wizzra
Perhaps the problem is the memory allocation system you are using. Try to avoid heap alloc functions (slow!), and remember that every allocation is done in a multiple of 4k (system's granularity). So if you call GlobalAlloc (internally uses a heap), for example, then it would be the slowest method, and to store a 1 byte string, you are wasting 4095 bytes of NULLs... :(
Posted on 2003-08-20 18:02:17 by QvasiModo

Perhaps the problem is the memory allocation system you are using. Try to avoid heap alloc functions (slow!), and remember that every allocation is done in a multiple of 4k (system's granularity). So if you call GlobalAlloc (internally uses a heap), for example, then it would be the slowest method, and to store a 1 byte string, you are wasting 4095 bytes of NULLs... :(


Thats the problem I was wondering about as well, how to allocate the memory, one idea was to make a "fat" type alloc, use it to split up larger allocs. Then indexing through that would be merely asking for which chunk in the fat list

IE: A "used" and "unused" pool, that'd contain memory addresses of where the memory isn't being used and how much of it is there, then when something is added, it's chopped up, leaving the used pool with an entry and the unused pool with a changed entry, when a deletion happens, it merely takes the entry out of the used list and adds it to the used list (absolutely no freeing of memory), only thing is, there'd have to be a format for fragmentation, whereas you can utilize the memory better. Another idea would be to have a function to set up the memory, add more fat, clean up and a get item and a put item, so the routines would properly distribute the item into chunks of memory until it was done (and allocate more area and a new fat if need be).

I know, that sounds insane, but it's about the only means to do it. Now if I can only figure out the specs on that AND impliment it.
Posted on 2003-08-21 11:53:34 by FunkyMeister

Perhaps the problem is the memory allocation system you are using. Try to avoid heap alloc functions (slow!), and remember that every allocation is done in a multiple of 4k (system's granularity). So if you call GlobalAlloc (internally uses a heap), for example, then it would be the slowest method, and to store a 1 byte string, you are wasting 4095 bytes of NULLs...

Say... what?
Only VirtualAlloc has 4096 byte granularity. I can't remember the granularity of Heap*, but it's small enough that it's not a problem for things you need dynamic allocation for. Also, heap memory allocation speed is usually quite fine - unless you have an insane amount of small allocations, or repeated de/reallocations.
Posted on 2003-08-21 12:04:57 by f0dder



Thats the problem I was wondering about as well, how to allocate the memory, one idea was to make a "fat" type alloc, use it to split up larger allocs. Then indexing through that would be merely asking for which chunk in the fat list

IE: A "used" and "unused" pool, that'd contain memory addresses of where the memory isn't being used and how much of it is there, then when something is added, it's chopped up, leaving the used pool with an entry and the unused pool with a changed entry, when a deletion happens, it merely takes the entry out of the used list and adds it to the used list (absolutely no freeing of memory), only thing is, there'd have to be a format for fragmentation, whereas you can utilize the memory better. Another idea would be to have a function to set up the memory, add more fat, clean up and a get item and a put item, so the routines would properly distribute the item into chunks of memory until it was done (and allocate more area and a new fat if need be).

I know, that sounds insane, but it's about the only means to do it. Now if I can only figure out the specs on that AND impliment it.


Makes sense, it would be pretty similar to how (I imagine) a heap is implemented in Windows, except it would allow fragmentation. The FAT-like idea is better, I had thought of a linked list but it would be slower (deletion of an item would require to update the headers of each node, while a keeping a main index allows you to make all changes in the same place. Implementation shouldn't be really hard, just time comsuming (just imitate the way DOS works, and searching is even faster because you don't have to traverse a list, instead you calculate all the addresses since it's really a complicated array). I'll try to implement that, even if it isn't fast enough for this project it will serve well as a fast heap replacement.
Posted on 2003-08-21 17:54:42 by QvasiModo

Say... what?

Oh, no... I said something stupid again :grin:
Only VirtualAlloc has 4096 byte granularity. I can't remember the granularity of Heap*, but it's small enough that it's not a problem for things you need dynamic allocation for.

I didn't know that... too bad I don't have win32.hlp here, but I think it didn't say anything about a heap's granularity. Actually I just assumed it would be the same as VirtualAlloc. :o
Also, heap memory allocation speed is usually quite fine - unless you have an insane amount of small allocations, or repeated de/reallocations.

But f0dder, that sounds like an exact description of this problem! :rolleyes:
http://www.asmcommunity.net/board/index.php?topic=13691&perpage=15&pagenumber=4
http://www.asmcommunity.net/board/index.php?topic=6314
http://www.asmcommunity.net/board/index.php?topic=6385
Posted on 2003-08-21 18:04:09 by QvasiModo
One more stupid graphics bug to the list :mad:
This time Windows Millenium 4.90.3000
Posted on 2003-08-21 19:15:42 by QvasiModo

One more stupid graphics bug to the list :mad:
This time Windows Millenium 4.90.3000


According to Micro$oft, thats not a bug, it's an issue.

(Someone grab me a tissue...)

As for the fat idea, I've been mulling it over some, going to see if I can proto the format some and stream line it for ease of coding. Not sure if I want to make a defrag method, maybe when the free happens, check other free'd segments to see if they can be merged. Hmm, maybe I'll do that during allocs, then that way, frees won't take much time. :) I was thinking a background thread to do cleanup, but then I'd have to "lock" the fat to do that, which would not prove any worth, because if I modified the list while an alloc or free happened, it'd be a mess.

Still trying to figure out what features to put into the design so it won't outdate it self fast.

I've been re-inventing the wheel far too much on this and I want to do it one more time, completely.
Posted on 2003-08-23 10:08:51 by FunkyMeister
Hi, I'm back from a nearly one week episode of flu (not completely over yet :grin: ).
I'm posting here my (probably last) version of the treeview thing. I got bored, really. If someone comes up with the solution to the double click problem I'll update, but I don't feel like working on it anymore. :(
As for the listview problems, how is it going? Are you implementing the FAT idea? We could do it here in the board, since code for a custom heap could be reusable, it would help a lot of people (and sure would be fun to code it :) ).
Posted on 2003-08-29 15:07:16 by QvasiModo
BTW, the granularity of HeapAlloc is exactly 12 bytes (at least under Win98, but I guess it's not something likely to change from one Windows version another). I've made this little test proggy to test it...
Posted on 2003-08-29 15:10:34 by QvasiModo