The MASM Forum

A current project of mine is going to need some list management. This is something I've done before, but it's always something of a pain; I end up doing a lot of scribbling with pencil and paper before figuring it out.

The data structure is super-simple: it's just a list (a linear list, not linked) of structures:
$TL STRUCT
  dispTxtPtr DD ?
  insertTxtPtr DD ?
  tlType DD ?
$TL ENDS
This defines a "tool list" for my editor. The list is constructed by reading an initialization file and writing structure elements to a list in heap memory. So far, so good.

Thing is, I want to be able to manipulate this list: insert new elements between existing ones, or at the head or tail; move elements up or down and delete elements. This will be accomplished in code by setting source and destination pointers and doing block moves (REP MOVSx comes in real handy here).

I'll be able to do this after a lot of head-scratching and drawing boxes on paper. But I'm thinking, maybe this is a case where it would be nice to have a library that could take care of these operations. I'm sure it could be done as a general-purpose tool, where elements of any size could be moved around.

Well, something to think about. Maybe I'll start on that.

I usually use 2 memory blocks, one for the 'objects' themselves, and one for a list of addresses to them.
That way, you manipulate the address list, which works no matter the object size.
By growing the address list memory you can increase the number of 'slots' for objects.

Quote from: NoCforMe on January 31, 2024, 03:03:00 PMit's just a list (a linear list, not linked) of structures

On lists: (https://www.studysmarter.co.uk/explanations/computer-science/data-structures/list-data-structure/)

QuoteIn many programming languages like Python, this data structure is commonly known as an array.

Why not a simple array? What can you do with a list that you can't do with an array (and vice versa)?

Quote from: NoCforMe on January 31, 2024, 03:03:00 PMWell, something to think about. Maybe I'll start on that.

 :biggrin:  Don't think too much, is just an array.

You can work with pointers or just an index.

OK, this morning at breakfast I sketched out the beginnings of my scheme.

I'll call the whole package LMlib (for "list management").

Master structure:
LMINFO    STRUC
  structSize    DD ?        ;In case a new version comes along at some point ...
  baseAddr    DD ?          ;Addr. of allocated list.
  elementSize    DD ?
  numElements    DD ?
  maxElements    DD ?       ;For checking for overflow
LMINFO    ENDS
Functions:

• LMinit():    initializes everything, allocates memory for list
• LMnew():    adds a new element at the end of the list
• LMinsert():    inserts a new element @ [index]
• LMdelete():    deletes an element
• LMmove():    moves an element to a new location
• LMdealloc():    deallocates list memory

Example usage:
    MOV    LMI.structSize, SIZEOF LMINFO
    MOV    LMI.elementSize, <element size>
    MOV    LMI.maxElements, <max. # elements>
    INVOKE    LMinit, ADDR LMI

    INVOKE    LMinsert, ADDR LMI, ADDR <new element>, index

    INVOKE    LMmove, ADDR LMI, ADDR <element to move>, index

I suppose LMnew() could just be considered a special case of LMinsert(), where index is at the end of the list.

Quote from: jj2007 on January 31, 2024, 08:27:32 PM

Quote from: NoCforMe on January 31, 2024, 03:03:00 PMit's just a list (a linear list, not linked) of structures

On lists: (https://www.studysmarter.co.uk/explanations/computer-science/data-structures/list-data-structure/)

QuoteIn many programming languages like Python, this data structure is commonly known as an array.

Why not a simple array? What can you do with a list that you can't do with an array (and vice versa)?

Terminology alert:
Let's not get bogged down here in semantics. When I say "a list", I mean a simple, non-linked list, i.e., an array. Same damn thing.

It's a dynamic list  :thumbsup: You have to save and to retrieve that from a file.

Quote from: NoCforMe on January 31, 2024, 03:03:00 PMmaybe this is a case where it would be nice to have a library that could take care of these operations

Absolutely - see Dim (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1126), Insert (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1131) and Delete (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1135) :thumbsup:

include \masm32\MasmBasic\MasmBasic.inc
  Init
  Cls 3
  Dim rc() As RECT    ; whatever: DWORD, BYTE, REAL8, WNDCLASSEX, ...
  For_ ecx=0 To 9
    mov rc(ecx, left), ecx
    mov rc(ecx, top), Rand(100)
    mov rc(ecx, right), Rand(100)
    mov rc(ecx, bottom), Rand(100)
  Next
  m2m ecx, 5
  Insert rc(ecx)
  lea eax, [ecx+100]
  mov rc(ecx, left), eax    ; 105
  mov rc(ecx, top), Rand(100)
  mov rc(ecx, right), Rand(100)
  mov rc(ecx, bottom), Rand(100)
  Delete rc(7)
  PrintLine " left    top  right bottom"
  For_ ecx=0 To rc(?)-1
    Print Str$("%____i  ", rc(ecx, left)), Str$("%____i  ", rc(ecx, top))
    Print Str$("%____i  ", rc(ecx, right)), Str$("%____i\n", rc(ecx, bottom))
  Next
  MsgBox 0, "Arrays, yeah!!", "Hi", MB_OK
EndOfCode
Output:
left    top  right bottom
    0     28     25     40
    1     12     79     24
    2     71     57     93
    3     46     63     43
    4     51     77     28
  105      3     61     25
    5     18     40     37
    7     35     23     44
    8     45     94      2
    9      8     96     21

Quote from: NoCforMe on February 01, 2024, 08:08:41 AMWhen I say "a list", I mean ... an array

Thanks for clarifying that :thup:

Quote from: jj2007 on February 01, 2024, 10:44:46 AM

Quote from: NoCforMe on January 31, 2024, 03:03:00 PMmaybe this is a case where it would be nice to have a library that could take care of these operations

Absolutely - see Dim (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1126), Insert (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1131) and Delete (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1135)

I. Don't. Use. MasmBasic.

Quote from: HSE on February 01, 2024, 08:34:15 AMIt's a dynamic list  :thumbsup: You have to save and to retrieve that from a file.

????? Please explain; I don't understand.

Yes, it's a dynamic list, constructed from reading an .ini file. So what?

To me, a list is a list. (Not a linked list; that's a different critter.)

Quote from: NoCforMe on February 01, 2024, 12:27:05 PMI. Don't. Use. MasmBasic.

That's courageous :thumbsup:

There are the DSA_* functions (https://learn.microsoft.com/en-us/windows/win32/api/dpa_dsa/nf-dpa_dsa-dsa_create), but they have two problems:
a) they are clumsier and less powerful than Dim, Insert & Delete
b) it's an external library, so you'll have to deal with Bill Gates instead of me ;-)

Which is why I'll be rolling my own if I go ahead with this project. My own code I can trust.

Quote from: jj2007 on February 01, 2024, 02:08:43 PM

Quote from: NoCforMe on February 01, 2024, 12:27:05 PMI. Don't. Use. MasmBasic.

That's courageous :thumbsup:

There are the DSA_* functions (https://learn.microsoft.com/en-us/windows/win32/api/dpa_dsa/nf-dpa_dsa-dsa_create), but they have two problems:
a) they are clumsier and less powerful than Dim, Insert & Delete
b) it's an external library, so you'll have to deal with Bill Gates instead of me ;-)

DSA comes from Win OS, and have been there quite long, since NT born.
Dynamic Structure Arrays (https://www.geoffchappell.com/studies/windows/shell/comctl32/api/da/dsa/index.htm)

Quote from: TimoVJL on February 01, 2024, 08:10:57 PMDSA comes from Win OS

Yes indeed, and maybe I would have used DSA_* instead of rolling my own array stuff (Dim, Insert, Delete, Erase, Swap) if I had known them 15 years ago. Strangely enough, they have never been used in this forum, except for two posts by Edgar alias Donkey in 2008 (https://www.masmforum.com/board/index.php?msg=74327) and 2011 (https://www.masmforum.com/board/index.php?msg=135185).

The point here is the artificial distinction between "built-in" and "third party". Yes, DSA_* is "built-in", and yes, MasmBasic is "third party", but so is the Masm32 library that almost all the forum members (well, those who do code...) use every day.

"Third party" is a bad word if it means "buggy and/or bloated and/or not maintained". What comes to my mind here are behemoths like QT. Or, to stay within the "built-in" category, the RichEdit control.

Would David refuse to work with the Masm32 library? Reinvent the wheel for things like print str$(eax)? Then I would congratulate him for his courage.

Posting "it would be nice to have a library" and, when shown that such a library exists already, responding in fat letters "I. Don't. Use. MasmBasic." is a bit ridiculous. I wish him luck rolling his own. It's years of hard work programming that stuff in Assembly. I'll watch his progress with great amusement.

Quote from: jj2007 on February 01, 2024, 10:22:00 PMThe point here is the artificial distinction between "built-in" and "third party". Yes, DSA_* is "built-in", and yes, MasmBasic is "third party", but so is the Masm32 library that almost all the forum members (well, those who do code...) use every day.

Would David refuse to work with the Masm32 library? Reinvent the wheel for things like print str$(eax)? Then I would congratulate him for his courage.

Welll, regarding the Masm32 library, the only function I've ever used from that is the one that extracts "command-line" arguments (GetCL()). I do roll my own for everything else. (Remember my motto: "Assembly language should be fun!")

Now obviously I'm not a production programmer; if I was I'd certainly be using more "external" libraries, perhaps even ones from MasmBasic. But I'm not, and I actually prefer my own home-grown code where it's possible. (If it comes to complex stuff like, say, dealing with JPGs, then I certainly look for existing codebases.)

For things like your example, print str$(eax), I find that wsprintf() takes care of all my needs.

Quote from: NoCforMe on February 02, 2024, 06:41:58 AMWelll, regarding the Masm32 library, the only function I've ever used from that

I see you made good use of our libraries in your Lissajous project :thumbsup:

INVOKE atodw, ADDR buffer ; line 380
INVOKE atodw, ADDR buffer ; line 389
INVOKE FpuAtoFL, ADDR buffer, ADDR floatField1, DEST_MEM ; line 441
INVOKE FpuSin, ADDR floatField1, ADDR floatField2, SRC1_REAL
INVOKE FpuMul, ADDR floatField2, SinScaleValue, ADDR floatField1...
INVOKE FpuTrunc, ADDR floatField1, ADDR xPos, SRC1_REAL OR DEST_IMEM
INVOKE FpuAtoFL, ADDR buffer, ADDR floatField1, DEST_MEM
INVOKE FpuSin, ADDR floatField1, ADDR floatField2, SRC1_REAL
INVOKE FpuMul, ADDR floatField2, SinScaleValue, ADDR floatField1,...
INVOKE FpuTrunc, ADDR floatField1, ADDR yPos, SRC1_REAL OR DEST_IMEM

Oh yeah, forgot about Raymond's indispensible FPU stuff. I've since learnt how to use the FPU directly, but yes, they definitely come in handy (if you're not that concerned about speed).

Here's my first cut of the LM (list management) package. Testbed program included.

Functions:

• LMinit(): Allocates heap memory for list
• LMinsert(): Inserts a new list element into list
• LMdelete(): Deletes a list element
• LMmove(): Moves a list element up or down in list
• LMreplace(): Replaces a list element's contents
• LMdealloc(): Deallocates heap

There's a "master structure" (LMINFO) which contains data needed for all operations, created by the caller and passed to each function. The structure contains "bookkeeping" members which give the number of elements and bytes used and free.

The testbed program (LMtest) lets you exercise these functions (except for LMdealloc()). Try it out. It's been minimally tested, seems to work OK so far. To insert new elements, select the element you want to insert before in the listbox, type some identifying text into both edit fields, select LMinsert() in the combobox and hit the "Make It So" button. (Select "LMinsert($LM_InsAtEnd)" to insert at the end of the list.) The maximum # of elements is set to 10 so I could see if the code that checks for a full list works. You can change this in the source, of course.

Let me know what you think. One thing: the move function (LMmove()) moves one element up (towards the beginning of list) or down one "notch". This suits my purposes for this package. I thought of making this function able to move any element to any "slot", which I could do, but I'm not sure this would actually be useful. Let me know your thoughts on this.

Hi NoCforMe
Really good stuff! Well written, documented and works well.  :biggrin:
Nice that you wrote an application to test it.

Looking at the code, I see that you are using different methods to move the data.
LMinsert is where most of the fun happens. To open a gap you use a loop that moves bytes and in other cases you use "REP MOVSB".
Depending on the data size you are aiming for, there are some better and more efficient (speed-wise) methods to do this.

Well done!  :thumbsup:

Regards, Biterider

Thanks. I should point out that for this code I really don't care that much about speed, at least whatever microseconds of difference there may be between using MOVs and using REP MOVSBs. The reason I used MOVs in LMinsert() is because I have to step backwards through the list, whereas in LMmove() and LMdelete() I can use the string instruction since I'm going forwards. (Yes, I realize I could set the direction flag to go backwards, but I like the way I'm doing it here better.)

With any uses of this package that I can think of, I can't see any good reason to be obsessed with speed here. I did try to be conscientious about error checking. If someone wants to use this and optimize it for speed, be my guest.

Quote from: NoCforMe on February 04, 2024, 04:28:25 PMLet me know your thoughts on this.

Solid work :thumbsup:

Re speed, I'm using RtlMoveMemory for Insert (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1131)(), which in turn uses rep movsd under the hood. The movdqa + movntdq combo is faster for huge allocations, but I wouldn't lose time over it ;-)

Quote from: jj2007 on December 14, 2021, 03:54:57 AMI changed my testbed to one big allocation (0.5GB), in order to minimise cache use. Now movntdq shines, of course, but rep movs is only about 15% slower:

Quote from: hutch-- on December 14, 2021, 09:01:47 AMIntel(R) Core(TM) i7-5820K CPU @ 3.30GHz (SSE4)
242232  kCycles for 1 * rep movsb
215571  kCycles for 1 * rep movsd
227473  kCycles for 1 * movlps qword ptr [esi+8*ecx]
230151  kCycles for 1 * movaps xmm0, oword ptr [esi]
146063  kCycles for 1 * movdqa + movntdq
146242  kCycles for 1 * movdqu + movntdq
146090  kCycles for 1 * movdqu + movntdq + mfence

So here's the thing about my data-movement code: yes, I know that if speed were an issue here, I could make it go mo' faster by, say, moving DWORDs, or even QWORDs instead of measly bytes.

However, that would complicate things greatly; now before any move you have to figure out how many units of what size to move, and who knows? that code alone might reduce some of your speed advantage. (I suppose you could figure this out in advance, say in the initialization routine, set a flag and then branch to the appropriate move code when needed.)

And what if the "elements" you're working with are like this?
SomeStruct    STRUC
   bigD        DD?
   lilW        DW?
SomeStruc    ENDS
Now you're limited to moving words. Worse yet:
SomeStruct    STRUC
   bigD        DD?
   lilB        DB?
SomeStruc    ENDS
which puts you back to moving bytes (or some super-complex scheme where you move a DWORD and then a byte). Sure, you could say this is poor data design, but who knows? maybe this is just what the user needs.

That's one reason I suggested you use a block of memory to hold pointers to your objects, it's easier to move a few DWORD pointers than arbitrarily-sized blocks. This way you could also store objects of different sizes, like strings.

That is a really good idea: add another level of indirection to the list of structures, just a flat pointer list which would add 4 bytes per element, not a huge burden. Adding elements would be easy, and of course rearranging the list by moving pointers rather than structure elements.

However, element deletion would still be a problem: easy to delete from the pointer list, but you'd either have to waste structure space by "stranding" them, or else rearrange the structure list itself (as I'm doing now) to salvage that space and then go through the pointer list and update it. In any case, do-able.

If you don't use any fancy switches for Windows, the high bit of an address is free to use since Windows will only allocate memory in the first 2GB. You could use that bit as a flag to indicate an empty slot and reuse it (and the old objects memory), or you could wait until you run out of slots and then do the garbage collection.

One reason for this whole thread was that I wanted to show what I had to go through to figure out the mechanics of handling lists, specifically inserting new elements. (Deleting elements poses similar problems.) Every time I implement a scheme like this I have to sit down with paper and pencil and draw things out so I can figure out how to set up source and destination pointers and move counts. Which was kind of the motivation to code up a package that would do this and eliminate all that head-scratching.

So I'm "showing my work" here:
(https://i.postimg.cc/67jDy8f0/LM-insert-scheme.gif) (https://postimg.cc/67jDy8f0)

I'm wondering how many of you can solve problems like this without resorting to doodling on paper. To those who can, my hat is off to you. I guess I'm just a mere mortal in this regard; obviously I'm not about to win any Nobel Prizes for advanced physics.

Hi NoCforMe
These data management constructs (lists, vectors, collections, ...) are the cornerstones of more advanced applications and are well worth the time to develop.

As a source from where you can take some code and ideas I can offer you
https://github.com/ObjAsm/ObjAsm-C.2/blob/master/Code/Objects/Collection.inc (https://github.com/ObjAsm/ObjAsm-C.2/blob/master/Code/Objects/Collection.inc)
https://github.com/ObjAsm/ObjAsm-C.2/blob/master/Code/Objects/DataCollection.inc (https://github.com/ObjAsm/ObjAsm-C.2/blob/master/Code/Objects/DataCollection.inc)

or the recent code template discussion about vectors here
https://masm32.com/board/index.php?topic=11659.0 (https://masm32.com/board/index.php?topic=11659.0)

A more advanced concept used in combination with IOCP
https://github.com/ObjAsm/ObjAsm-C.2/blob/master/Code/Objects/DataPool.inc (https://github.com/ObjAsm/ObjAsm-C.2/blob/master/Code/Objects/DataPool.inc)

Regards, Biterider

Quote from: NoCforMe on February 05, 2024, 01:29:53 PMI'm wondering how many of you can solve problems like this without resorting to doodling on paper.

I can! But it costs me a lot of time to fumble code that would have been crystal clear with a piece of paper. Unfortunately I am too lazy to sit down and use a pencil.

If that's the case, JJ, I heartily recommend next time that you overcome your laziness and take out paper and pencil. Amazing how visualizing things can help you zero in on the correct solution quickly.

Continuing on, this is a part of my storage scheme that involves heap management, not list management, but since it's related I'm describing it here.

Here's what that list I've been playing with is used for: basically storing two strings, one a "display" string that shows on-screen, the other the "insert" string that gets inserted into the editor text when the user selects it. Pretty simple.

(https://i.postimg.cc/sB1FHS28/Heap-deletion.gif) (https://postimg.cc/sB1FHS28)

But now I'm adding a configuration editor to this scheme, which means that 1) strings can change length, becoming either shorter or longer, and 2) strings can be deleted. This poses problems.

If a string grows longer, it obviously can no longer live where it does in the heap, so the current heap entry will need to be abandoned (deleted) and a new one allocated. A shorter string can occupy the same space, perhaps with some left over (wasted).

So what do we do if a string grows or is deleted? Well, the easiest thing would be to do nothing, assuming we have enough room in the heap to waste space. But what if we want to recover that space?

One thing that occurred to me (actually last night in bed when I should have been sleeping!) was to use the string space in the heap to insert the string length; after all, we no longer need the string contents and can overwrite them, but we do need to know one crucial piece of info, namely how long the string is. So we can insert a 2-byte (WORD) length value there. Then when we need to allocate a new string (or when our garbage collector comes through the heap) we can use that value to see if there's enough space for the new string. (To make that work we'd have to "tag" the first byte of that word by setting the high bit to 1, and then be sure to strip off that bit when taking the value. This would work since no valid ASCII chararcter, at least in my scheme here, will have its high bit set.)

But there's a problem there (more lost sleep): We would have to ensure that there are at least 2 bytes available in each string. This isn't a problem for a non-NULL string, the shortest of which is 2 bytes, but what about a NULL string? That could just be a single byte (0). So we'd have to make sure that each string is at least 2 bytes long. That could work.

BTW, just to be clear, the length I'm talking about is not the string length obtained with strlen() but that value plus one to include the NULL terminator. (We're dealing with ASCII strings here, not Unicode.)

Just some more of the sticking points when designing storage strategies ...

Just let Windows worry about the heap?

I think by that you mean "just waste it", as I described above, is that right?

That's certainly a valid choice. You can always allocate more if you run out of space.

New string - HeapAlloc
Delete string - HeapFree
Resize string - HeapReAlloc

Windows uses a low-fragmentation heap, so it will take care of coalescing free blocks etc.
The downside is that there are a few bytes of overhead, so many small allocations might not work so well.

Quote from: sinsi on February 06, 2024, 08:28:37 PMmany small allocations might not work so well

The Windows heap is optimised for many small allocations (there is VirtualAlloc for bigger ones, although it never makes a difference, speed-wise). Still, there is overhead that slows things down.

There are two faster options:
1. the stack (by default, up to around 800kBytes, more if you use linker option /stack:nnnnh)
2. a ring buffer; used in MB e.g. for Print Str$(number1), "<>", Str$(number2)

Both have the advantage that no *Free is needed.

Speed-wise, all three options are most of the time sufficient: you rarely use HeapAlloc in a speed-critical innermost loop. Tests with StackBuffer() (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1255) show that it has an advantage over HeapAlloc for about 0-500kBytes; above that value, HeapAlloc is equally fast or slightly faster (YMMV).

I have successfully incorporated my LM (list management) module into my editor, the latest version of which is available in this post (https://masm32.com/board/index.php?msg=127129).

Quote from: jj2007 on February 06, 2024, 08:56:43 PMThe Windows heap is optimised for many small allocations (there is VirtualAlloc for bigger ones, although it never makes a difference, speed-wise). Still, there is overhead that slows things down.

There are two faster options:
1. the stack (by default, up to around 800kBytes, more if you use linker option /stack:nnnnh)
2. a ring buffer; used in MB e.g. for Print Str$(number1), "<>", Str$(number2)

I just don't get it.

What is it with your obsession with speed here? To me, that's the last thing I'd be looking at when it comes to memory allocation. What I would want out of a memory allocator is

• Efficiency of allocation; minimal memory wasted
• Reliability and good error handling

Quote from: NoCforMe on February 16, 2024, 08:48:57 AMWhat is it with your obsession with speed here?

Quote from: sinsi on February 06, 2024, 08:28:37 PMmany small allocations might not work so well

I wouldn't accuse Sinsi of being obsessed with speed, but his only argument against using the heap was, indeed, speed. Do you get it now?

Quote from: NoCforMe on February 16, 2024, 08:48:57 AMEfficiency of allocation; minimal memory wasted

Why are you so obsessed with memory? I have 16GB of it.

Quote from: jj2007 on February 16, 2024, 11:02:24 AM

Quote from: NoCforMe on February 16, 2024, 08:48:57 AMEfficiency of allocation; minimal memory wasted

Why are you so obsessed with memory? I have 16GB of it.

Sure; I've got 5Gb, which ain't chicken feed either.

However, someone else who has some gigantic memory-intensive application would be quite concerned with efficient usage of memory. Not me, but others. Speed, probably not so much.

Somebody with a "gigantic memory-intensive application" would be extremely concerned with speed, for obvious reasons.

Actually, my point was about memory - if you allocate lots of 4-byte blocks, there is at least an 8-byte overhead associated with it, so every 4 bytes you allocate actually uses 12. Of course, this is an extreme case :biggrin:

Quote from: sinsi on February 16, 2024, 01:02:52 PMif you allocate lots of 4-byte blocks, there is at least an 8-byte overhead

Point taken :thumbsup: