hey guys...

I would just like to know what would be the best approach to allocate an uncertain ammount of memmory objects, each being 6100 bytes in size. Heap functions allows you up to 4MB and you can realocate it - but i will need more than this. VirtualAlloc give me a larger range but i can't reallocate this value (or can i?). File Mapping seems to be great but same problem as VirtualAlloc.

(most cases the required size will be about 6MB but it might also be 16MB in the next case)

Thank you,
Black iCE
Posted on 2004-08-06 19:51:29 by Black iCE
Memory allocated with VirtualAlloc is expanded by passing the top of the buffer as the base address :
; Let the system decide where to put it the first time, allocate 1MB

invoke VirtualAlloc, NULL, 0100000h, MEM_COMMIT, PAGE_READWRITE
mov [pArray],eax
add eax,0100000h
mov [MaxPTR],eax

; Now every time you want more memory you can expand it
; just be sure to verify that it was available
invoke VirtualAlloc, [MaxPTR], 0100000h, MEM_COMMIT, PAGE_READWRITE
add [MaxPTR],0100000h
Posted on 2004-08-06 20:13:03 by donkey
Once again saved by donkey:alright:

Thank you - i got it. It works according to a range {max,min} and so you move the {max} on and on when you need more memory.

Thank you!
Black iCE
Posted on 2004-08-06 20:22:33 by Black iCE
Ice, I think you might be a bit confused about HeapAlloc. You can easily allocate huge blocks if you want, the "4 megabyte" thing is just a recommendation (not a hard limit) for 9x - and it's for individual blocks, not total allocation.

So for 6100-byte sized objects, HeapAlloc should be just fine, unless you have some specific requirements (speed, fragmentation, ...). If you go for VirtualAlloc, remember to implement an allocation system. If you use VirtualAlloc calls for each 6100 byte objects, you'll waste a lot of memory - each size is rounded up to 4kb, and are allocated at 64kb-aligned addresses by default...
Posted on 2004-08-07 03:38:39 by f0dder
F0dder, thank you for the info - as i still need to learn a great deal of things. I suppose that - yes, speed is my consirn. BTW i try alloc chunks and not for each 6100-byte object. But truly - thank you for clearing that up (heap-limit) for me. MSDN seems to say things very vaguely
Posted on 2004-08-07 15:48:15 by Black iCE
If speed is a big concern, then allocating bigger chunks and managing those chunks yourself is a good idea - it should be possible to come up with a specific strategy that's better than the generic one in windows, especially when you have fixed-size objects.
Posted on 2004-08-07 16:38:27 by f0dder
F0dder - well i then would like to ask you about the proposed way you would do it. Just an exaple to show me past those generic windows routines. Can you please just give me a hint. :alright:

Procudo (spelling) will be gr8.

Black iCE
Posted on 2004-08-07 16:50:23 by Black iCE

F0dder - well i then would like to ask you about the proposed way you would do it. Just an exaple to show me past those generic windows routines. Can you please just give me a hint. :alright:

Procudo (spelling) will be gr8.

Black iCE


This isn't the most efficient method by any means but it will get you started into think about more ways.

Let's say you have "chucks" of 6100 bytes each and you know you won't need more then 64 of these at any given time. We'll actually allocate 6144 per chuck to keep it aligned nicely.

So, allocate a buffer of 6144 * 64 + (? * 64). The ? is some index type into which "sections" are available to use or already in use. ? = bits, bytes, etc.

Use the last section (the ? * 64) to keep track of what "chucks" are in use. The rest of the buffer is your usable space that you return pointers to. Make sure you keep your indexes of used sections at then end so you can keep your buffer segments aligned nicely.

This type is what I use on one of my programs. I use a BYTE to keep track if it is in use or not and then do a fast "strlen" type search to find the first available spot to use.

Hopefully, this will get you thinking or at the least, other people to suggest other ways.

Relvinian
Posted on 2004-08-07 22:54:07 by Relvinian
Nice to see that you are looking though the board.

i would like to clarify, that the item's that i enumerate is shellobjects - and so i have no idea of the ammount of files/directories/regitems that would be in one specified directory. I think the max in fat32 or ntfs would be about 0xffffffff. So then using a non-windows approach makes me somewhot quezy. Just cause you replayed saying about if you know... well i don't.

The size of the object is infact a custom struct that keeps the info that i will use about each item in the memmory. So insead of having one thread i have made two witch both will help me in my implementation. But - by the looks of it i'll stick to virtual listviews. (i see you have replayed there too).

I just wanted to see what the ASM way is of alloc memmory (dynamically) and from there i'll use it. Don;t want to be spoon fed but i'll apriciate a shove in the right direction. Coming from a HLL background.

Kindly,
Black iCE
Posted on 2004-08-07 23:02:59 by Black iCE

Nice to see that you are looking though the board.

i would like to clarify, that the item's that i enumerate is shellobjects - and so i have no idea of the ammount of files/directories/regitems that would be in one specified directory. I think the max in fat32 or ntfs would be about 0xffffffff. So then using a non-windows approach makes me somewhot quezy. Just cause you replayed saying about if you know... well i don't.

The size of the object is infact a custom struct that keeps the info that i will use about each item in the memmory. So insead of having one thread i have made two witch both will help me in my implementation. But - by the looks of it i'll stick to virtual listviews. (i see you have replayed there too).

I just wanted to see what the ASM way is of alloc memmory (dynamically) and from there i'll use it. Don;t want to be spoon fed but i'll apriciate a shove in the right direction. Coming from a HLL background.

Kindly,
Black iCE



Even if you don't know, as long as you keep your "counters" at some easy place to get to (like at the end), you can always use HeapReAlloc to allocate the memory for more space and then "move" the counters to the new end. Of course, make sure you lock the memory while doing something like this for thread safety. :)

But anyway you come up with will work. :)

Relvinian.
Posted on 2004-08-07 23:06:17 by Relvinian
Rereading your post - well, i get the just of it and i appricate your help - and it is what i ask for so thank you.
Posted on 2004-08-07 23:06:27 by Black iCE
What interisted me was F0dder saying about non-window approach and that got my interist and so i'll am just wandering about the way to do this.... given the first post senario. That is why i as for the shove in the right direction.
:grin:

Black iCE
Posted on 2004-08-07 23:09:28 by Black iCE
6100 bytes? use the stack, fast and dynamic (within reason of course), and much smaller than the rest.

sub esp,6100

mov [mem],esp

or

mov reg32,esp


:)
Posted on 2004-08-08 10:43:56 by Drocon
Stack probably isn't a very good option here - iCE needs to allocate multiple 6100-byte items. There might also be some object lifetime/scope things that make stack unsuitable.

Okay, so you're dealing with shell objects... for files? This means you have to have a dynamic scheme without hard limits (you probably COULD get away with hard limits, but it's a bad idea.) It also means you will usually have a "relatively small" amount of objects, and that you're probably so I/O bound that allocation speed won't matter too much.

If I've understood you correctly (ie, shell objects for filesystem files), I would probably go for a "delta-growing array" approach... keep two DWORDs for current and maximum items in the array. When you add an entry, check if current==maximum. If so, increase maximum by your "delta", or multiply maximum by a "magic constant".

You'll want to grow the array enough that you avoid heap fragmentation, but not so much that you waste big amounts of memory. You're probably not going to do a lot of bulk data processing of the shell objects, so using alignment as relvinian suggested will probably just be wasteful in this example.

If you expect between 6-16 megabyte, wasting a megabyte or two won't be too bad, and better than heap fragmentation anyway... so a delta value of 350 wouldn't be too bad.

And of course you could use VirtualAlloc instead of HeapAlloc, this would avoid heap fragmentation and it isn't that much more bother to implement.

There are other things to consider, too - like whether you should ever shrink the allocated memory block... what's the typical scenario where you need this memory allocation? A file browser, or something that builds a list of all files on the harddrive, or something completely different which means I've totally misunderstood what you're doing? :-)


Donkey's approach with VirtualAlloc is probably the simplest, as you don't need to worry about heap fragmentation and such... however, if you need multiple parallel allocations, or use libraries that depend on VirtualAlloc, you can no longer be guaranteed contiguous memory, and suddenly things become somewhat complicated :)
Posted on 2004-08-08 12:14:36 by f0dder
hey f0dder,

Yes - i need it for a file browser. So the lifetime of the object can vary (did think about that thanks for pointing this out to me). ShellObjects well general term i use when i also include non-filesystem objects like the contents of My Computer, they are a group of registry items acting as file-objects to the windows user. (But i assume you know that :)).

"delta-growing array" growing approach - but isn't that what VirtualAlloc is capabil of (looking at donkey's post).

"If you expect between 6-16 megabyte, wasting a megabyte or two won't be too bad, and better than heap fragmentation anyway... so a delta value of 350 wouldn't be too bad." - f0dder

i always assume the worst, but yes i agree it wouldn't be bad, but....

"here are other things to consider, too - like whether you should ever shrink the allocated memory block.." - f0dder

Yes i will need to shrink this memory block... so "house cleaning" is something that i try to do most of the time. Plus i am considering allowing a couple of threads to browse into the subfolders to get a count of the shellobject so that i can calculate the required memory without having to re-allocate it all the time. Also with the use of IShellIcon methods of icon extraction but then there is always the slow SHGetFileInfo that i could use but as i said that speed is somewhot critical at the moment. A test directory is the windows xp install (i386) or the System32 that takes normally about 12 seconds to show in the non-virtual listview. (so that is extremly slow and i am trying to speed it up... not using a virtual-listview so that is the way i have gone now and implemented a virtual listview and now this question had crept up on me).

Kindly,
Black iCE
Posted on 2004-08-08 12:39:33 by Black iCE
Another problem that is encountered is when IShellIcon methods can't retrieve the icon and then i must use IExtractIcon... i have used it before... not coded up to there yet but the issue is ofcourse the fact that when i take a look in TaskManager the memory used can just grow and grow to HUGE ammounts and once the opertaion is compelted it is all released. So if there are any other alternatives to extract an icon from exe etc relativly fast without huge memory allocation in once case the cpu usage was 100% and the pagefile grew a 100mb :(. Is it such a task in windows? I suppose that when i finnally get there i'll just extract what is visible the the listview and then ask the listview to keep it internally.... not sure about that either.
Posted on 2004-08-08 13:15:41 by Black iCE

"delta-growing array" growing approach - but isn't that what VirtualAlloc is capabil of (looking at donkey's post).

Sure is :) - it can be implemented with both VirtualAlloc and HeapAlloc. The advantage of HeapAlloc is that you're always guaranteed that the array can grow (by moving memory around if necessary), with VirtualAlloc you'd have to add "a bunch of extra code" to handle this.


i always assume the worst, but yes i agree it wouldn't be bad, but...

Allocating "some amount" too much is often better than a fragmented heap. In extreme cases, heap fragmentation _could_ to you not being able to allocate a new block...


Yes i will need to shrink this memory block... so "house cleaning" is something that i try to do most of the time.

It might be more efficient not to shrink the block sometimes - or to never shrink it below "some amount of entries"... again, to avoid unnecessary alloc/dealloc calls, and heap fragmentation. But it would also be bad to have allocated memory for, say, 10.000 objects if you only have a couple hundred most of the time.


Plus i am considering allowing a couple of threads to browse into the subfolders to get a count of the shellobject so that i can calculate the required memory without having to re-allocate it all the time.

Could be a good idea - remember to adjust the priority of these threads to something lower than your main thread(s).


Also with the use of IShellIcon methods of icon extraction but then there is always the slow SHGetFileInfo that i could use but as i said that speed is somewhot critical at the moment.

Do it the way Explorer does it - run in a background thread, update icons as they become available, and use a "default icon" until then. Gives the illusion of being faster, while it will actually be a tiny bit faster. Works well in practice. Also, you could keep a caching scheme... (even though windows already has icon cache).
Posted on 2004-08-08 13:53:41 by f0dder
Thank you f0dder, you have addressed some issues that will help me a great deal. I am really greatful for your help. Thank you :)

- so i'll use Icon extraction on failed attempts with IShellIcon in a background thread to retrive the propper icons :)
- start browser in My Computer cause a minimal # of objects are ensured there.
- Thread out into subfolders to predict memory allocation and requirements
- HeapAlloc the memory chunks

- *anything else i missed* :D

added list and fixed a spelling mistake

Black iCE
Posted on 2004-08-08 14:02:32 by Black iCE
Black Ice,

Since you are saying that it takes for ever to insert items into your ListCtrl, I decided to do a test and see how long it would take to insert my C:WindowsSystem32 directory (which is an XP system). The count of files for that directory is: 6299 files, 211 folders.

Here's the stats for a very quick and dirty c++ code using VC++ 6.0 on a P4 2.53ghz machine to insert the file and folder names into a ListCtrl (non-virtual style)

CBrowserView::OnInitialUpdate(): 6.400ms
CBrowserView::OnInitalUpdate() + any child functions: 143.222ms

Here's the code:


void CBrowserView::OnInitialUpdate()
{
CListView::OnInitialUpdate();


// TODO: You may populate your ListView with items by directly accessing
// its list control through a call to GetListCtrl().
WIN32_FIND_DATA FileInfo;

CListCtrl& theCtrl = GetListCtrl();
HANDLE hFind = ::FindFirstFile(_T("c:\windows\system32\*.*"), &FileInfo);
if (hFind != INVALID_HANDLE_VALUE)
{
int idx = 0;

theCtrl.SetRedraw(FALSE);
do
{
theCtrl.InsertItem(idx++, FileInfo.cFileName);
} while (::FindNextFile(hFind, &FileInfo));
theCtrl.SetRedraw();

::FindClose(hFind);
}
}


As you can see, I just do a findfirst/findnext for every file (including directory names) and insert them into the ListCtrl (non-virtual style). I do turn off redrawing while I'm inserting them though and turn the drawing back on afterwards.

So, with that in mind, you said in one of your messages that it takes 12 second to process your system32 directory. A couple things come to mind on this:


1) How are you implementing the findfirst/findlast to populate your listctrl.
2) What other items are you processing other then just putting the name of the file/folder into the listctrl that could be done in background threads?
3) How fast is your CPU and harddrive?

Relvinian
Posted on 2004-08-08 15:53:32 by Relvinian
I use Shell COM methods - IShellFolder::EnumObjects, Also i admit that yes i havn't done the WM_SETREDRAW. OK the CPU is a 500 MHz that i tested this on. I am using a diffrent pc at the moment and i was recalling some of my problems that i have encountered while trying to do it last year. As i am attempting to do the same now - i reconed that i might ask before i stuffup again. Secondly you look to be using MFC, well honestly i neva graspt it and so i am stuck with SDK although i played around with ATL. Note this test was run in debuggin' mode so yes i guess the value is somewhot inapropiate (found out later with another app that there is a diffrence).

::Other things done
- i am obtaining the icons of the shell objects through Shell COM. (use IExtractIcon when IShellIcon failes)
- i am using the LPARAM to keep the values returned of each individual item from IShellFolder::GetAttributesOf to use for icon display and capability checks.
- Sorting the items after the IShellFolder::EnumObjects is returned. (i must admit that i didn't first cache them and that i know it my greatest mistake cause i could sort them in memory or rather add them to the listview in the order that suits me.) this is where i had the most time spent on

So i was getting rather fedup after doing this for the 4th time that i though i'll rather ask then be diapointed again.

PS - everything that i know of programming is what i have picked up from here or there...

Using Shell COM Methods to make a seemless transaction from the desktop to the disk and viseversa.

{comapring that value to what explorer gets...}

Well thank you.
Black iCE
Posted on 2004-08-08 16:28:43 by Black iCE