Dynamic string array

[hutch--]

I have been playing with this one for a while, here is the first attempt. This version requires the array member count to be used as an argument for each macro/function but I think it would be easy enough to write the count in the first array member and make the array a 1 based rather than zero based string array.

Code Select Expand


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    include \masm32\include\masm32rt.inc
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

comment * -----------------------------------------------------
                        Build this  template with
                       "CONSOLE ASSEMBLE AND LINK"
        ----------------------------------------------------- *

      arralloc$ MACRO member_count

        LOCAL lbl0

        push ebx
        push esi
        push edi

        mov eax, member_count                   ;; member count in EAX
        add eax, 1                              ;; increment member count
        lea eax, [0+eax*4]                      ;; mul by 4 for memory size
        mov esi, alloc(eax)                     ;; allocate GlobalAlloc() memory for pointer array

        xor ebx, ebx                            ;; use EBX as index
      lbl0:
        invoke SysAllocStringByteLen,0,4        ;; allocate 4 byte string
        mov DWORD PTR [eax], 0                  ;; set it to a zero length string
        mov [esi+ebx*4], eax                    ;; write its address to the pointer array
        add ebx, 1                              ;; increment index
        cmp ebx, member_count                   ;; check if it matches the member count
        jle lbl0                                ;; loop back if not

        mov eax, esi                            ;; return pointer array address in EAX

        pop edi
        pop esi
        pop ebx

        EXITM <eax>

      ENDM

      arrwrite$ MACRO arr,indx,txt
        invoke write_array_member,arr,indx,reparg(txt)
      ENDM

      arrfree$ MACRO arr,cnt
        invoke delete_array,arr,cnt
      ENDM

      write_array_member    PROTO :DWORD,:DWORD,:DWORD
      delete_array          PROTO :DWORD,:DWORD

    .code

start:
   
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

    call main
    inkey
    exit

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

main proc

    LOCAL pArr  :DWORD
    LOCAL acnt  :DWORD

    push ebx
    push esi
    push edi

; ÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷
;   write and display array members
; ÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷

    mov acnt, 100
    mov pArr,arralloc$(acnt)                    ; create the empty string array
  ; ---------------------------
  ; write "acnt" items to array
  ; ---------------------------
    xor esi, esi
  @@:
    arrwrite$ pArr,esi,str$(esi)                ; write each string to an array member
    add esi, 1
    cmp esi, acnt
    jle @B

  ; -------------------------
  ; display the array members
  ; -------------------------
    mov esi, pArr                               ; array address in ESI
    xor ebx, ebx
  @@:
    mov edi, [esi+ebx*4]                        ; load string address into register
    .if BYTE PTR [edi] != 0                     ; if 1st byte not 0
      print edi,13,10                           ; display the strings
    .else                                       ; else
      print "unused",13,10                      ; display that string is empty
    .endif
    add ebx, 1
    cmp ebx, acnt
    jle @B

  ; -------------------------

    arrfree$ pArr,acnt                          ; delete the members and pointer array

; ÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷
;   benchmark array allocation, write and delete
; ÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷

    mov acnt, 1000000                          ; 1 million members (0 based array)

  ; ==================================

    invoke GetTickCount
    push eax

    mov pArr,arralloc$(acnt)                    ; create the empty string array

    invoke GetTickCount
    pop ecx
    sub eax, ecx

    print str$(eax)," arralloc$ ms",13,10

  ; ==================================

    invoke GetTickCount
    push eax

  ; ---------------------------
  ; write "acnt" items to array
  ; ---------------------------
    xor esi, esi
  @@:
    arrwrite$ pArr,esi,str$(esi)                ; write each string to an array member
    add esi, 1
    cmp esi, acnt
    jle @B

    invoke GetTickCount
    pop ecx
    sub eax, ecx

    print str$(eax)," arrwrite$ ms",13,10

  ; ==================================

    invoke GetTickCount
    push eax

    arrfree$ pArr,acnt                          ; delete the members and pointer array

    invoke GetTickCount
    pop ecx
    sub eax, ecx

   print str$(eax)," arrfree$  ms",13,10

; ÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷·÷

    pop edi
    pop esi
    pop ebx

    ret

main endp

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

delete_array proc arr:DWORD,cnt:DWORD

    push ebx
    push esi
    push edi

    mov esi, arr                            ; array address in ESI
    mov edi, cnt                            ; member count in EDI
    xor ebx, ebx                            ; use EBX as index
  @@:
    cmp DWORD PTR [esi+ebx*4], 0            ; if not empty pointer
    je nxt
    free$ [esi+ebx*4]                       ; deallocate each array member
  nxt:
    add ebx, 1
    cmp ebx, edi
    jle @B

    free arr                                ; deallocate the pointer array

    pop edi
    pop esi
    pop ebx

    ret

delete_array endp

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

write_array_member proc arr:DWORD,indx:DWORD,txt:DWORD

    push ebx
    push esi
    push edi

    mov esi, arr                            ; load array address
    mov edi, len(txt)                       ; get the text length
    add edi, 4                              ; add terminator and
    and edi, -4                             ; extend to next 4 byte boundary
    mov ebx, indx                           ; place member index in EBX
    cmp DWORD PTR [esi+ebx*4], 0            ; test if member is allocated or blank
    je lbl
    free$ [esi+ebx*4]                       ; if allocated free it first
  lbl:
    mov [esi+ebx*4], alloc$(edi)            ; allocate string space
    invoke szCopy,txt,[esi+ebx*4]           ; copy text to allocated memory

    pop edi
    pop esi
    pop ebx

    ret

write_array_member endp

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

end start

[attachment deleted by admin]

[jj2007]

Impressive! arrwrite$ shows some non-linearity for acnt, see below.


100000
50 arralloc$ ms
10 arrwrite$ ms
50 arrfree$  ms


1000000
631 arralloc$ ms
190 arrwrite$ ms
511 arrfree$  ms


10000000
8833 arralloc$ ms
21031 arrwrite$ ms
5438 arrfree$  ms

[hutch--]

Thanks for the test jj, I saw much the same results. I used the OLE string capacity because the system can move them around in memory and I think this is what is happening when the count gets very high. GlobalAlloc() is a lot faster with the GMEM_FIXED flag but it would lead to severe memory fragmentation so I used the slower OLE string to solve the problem.

The next trick is to store the array count in the first array member and make it a 1 rather than zero based method and it also allows for economical bounds checking below 1 or above array count.

[Rainstorm]

core2duo 12.66Ghz 333mhz/4M winxp pro sp2
203 arralloc$ ms
125 arrwrite$ ms
234 arrfree$  ms

[jj2007]

MSDN: In 32-bit OLE, BSTRs use Unicode like all other strings in 32-bit OLE.

With the exception of...?

SysAllocStringByteLen:

Code Select Expand

Takes an ANSI string as input, and returns a BSTR that contains an ANSI string. Does not perform any ANSI-to-Unicode translation.
Visual C++

BSTR SysAllocStringByteLen( 
  LPCSTR  psz,   
  unsigned int  len 
);

psz
    A zero-terminated string to copy, or NULL to keep the string uninitialized.

len
    Number of bytes to copy from psz. A null character is placed afterwards, allocating a total of lenplus the size of OLECHAR bytes.
    Allocates a new string of lenbytes, copies lenbytes from the passed string into it, and then appends a null character.

Does SysReAllocString know that this is a byte/ANSI, not Unicode, string? MSDN is a bit vague...

[hutch--]

jj,

SysAllocStringByteLen() already does a realloc from the zero terminated string used as its first argument if you pass an address to it. SysReAllocString() is not needed in this context.