List type and arrays

[jj2007]

As with all additions to the Language:

• 1) larger executables (especially unwanted, for libraries: .a, .dll/.so)
  2) more complexity in compiler (=> longer compile time)
  3) therefore, more chances for "bugs" (nobody, wants that)
  4) chances that FBC becomes "bloatware"

1) a few hundred bytes more, if you use it
2) about 2-10 milliseconds more, per project
3) why that??
4) about 500 bytes more (0.04% of fbc.exe, 0.0001% of my current FreeBasic folder)

Still, you haven't elaborated on the "speed decrease".

[MrSwiss]

1) a few hundred bytes more, if you use it
2) about 2-10 milliseconds more, per project
3) why that??
4) about 500 bytes more (0.04% of fbc.exe, 0.0001% of my current FreeBasic folder)

Still, you haven't elaborated on the "speed decrease".

Just take every 10th user of FB, thinking "your way", but of course, with a different "favorite" addition ...
(just think a moment about it, the "now" used resources etc.)

Speed: see point 2 (end of story)

[Josep Roca]

If you don't use it, there won't be any increase in compilation speed or in the size of the executable.

The only advantage of not accepting suggestions is that the current lack of developers won't be a problem any longer. They won't be needed as there won't be nothing to do.

[MrSwiss]

They (developers) won't be needed as there won't be nothing to do.

Have you ever had a look, at the still "open" bug's-list, of the compiler?

[St_W]

I'd also like to see a native list implementation in FB, as it's a basic data structure that can be used in so many scenarios. However, to implement that properly some preconditions need to be fulfilled first: e.g. FB would need some form of generics. If this is added to FB we could implement our own list types without any macro hacks and it wouldn't even be needed to be integrated in the compiler (but e.g. could be shipped as header only library). Anyway, the implementation of generics is a major task (and even more complicated if it should be somewhat compatible with C++), so we probably won't see that anytime soon (due to the lack of compiler developers).

[Lost Zergling]

Hello,

jj2007, some more stuff about the problem on this subject : viewtopic.php?t=24648
Arrays are fast till you do not need to many redim otherwise using list appears to be usually a better choice.
Arrays are faster seeking than lists up to a specified numbers of values depending on the hardware specifications
The choice between array vs list will be depending on the size of the datas the algo needs to manage, the size the available memory, the way the memory is managed by system.

In Lists the purpose is to avoid as far as possible cAllocate, Deallocate or any low level reallocation.
This a crucial point when using cascaded indexation (a tree to access keys values)
So far, accessing a key "123456" is much more faster when accessing "12" then "34" then "56" in a tree structure because less lookups on values compared to a flat list, drawback is memory allocations/réallocations/deallocations slowing the system as the tree structure needs to be recomputed/maintained.
The more values in a list, the more the indexed (tree) structure will outperforms a flat list.
Other hand : the more the allocation is used, the more the system is sollicited at low level.
Problem is same with indexed arrays : Redim is slow

Conclusion :
Arrays vs List appears to be a question of optimization : both are usefull.

ps : St_W, I'm currently trying to go as fast as possible, hardest looks like behind me, stable & tested version planned within 2-3 months.

[jj2007]

jj2007, some more stuff about the problem on this subject : viewtopic.php?t=24648
Arrays are fast till you do not need to many redim otherwise using list appears to be usually a better choice.
Arrays are faster seeking than lists up to
...
Conclusion :
Arrays vs List appears to be a question of optimization : both are usefull.

Interesting stuff, you put a lot of work into that! I have set up a quick & dirty testbed, see Deleting selected elements from a string array, I would be curious to see if a linked list could compete with that.

Btw there seem to exist conflicting ideas about "Key Differences Between Array and Linked List", and some are just wrong:

4. Operations like insertion and deletion are time-consuming in arrays. On the other hand, the performance of these operations in Linked lists is fast.
5. Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.
6. In an array, memory is allocated during compile time while in Linked list it is allocated during execution or run time.
7. Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.
8. The requirement of memory is less due to actual data being stored within the index in the array. As against, there is a need for more memory in Linked Lists due to storage of additional next and previous referencing elements.
9. In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the array.

Here is an interesting read about "Linked-list has much better performance than array when it comes to random-insertion & random-deletion" - that was a good theory until they tested it ;-)

[Lost Zergling]

Interesting anyway jj2007.
There is no competition with Masm, therefore on a very specific & pretty different topic.
A string character can not be compared to a list item (variable lenght)
Basic programing style is mandatory. I'm everyday looking forward to something as easy as possible.
Too different stuff to make a comparison.

about performances the link you mention : "Conclusion
We should prefer array over linked-list when working with a list of small elements "
->How many elements ? A dynamic array supporting soft deletion is faster till the datas you expect to manipulate are not too much versatile (in size) !
My previous post "The choice between array vs list will be depending on the size of the datas the algo needs to manage, the size the available memory, the way the memory is managed by system."
Well I didn't mentionned caches (L1, L2,..) I have done different tests with different algo.
It is important to understand cache is a ressource, when you're using cache you're using a ressource, all the more difficult to compare.

[marcov]

So why would their be a decrease in performance if the ListType (as a whole implementation!) would be built into the Base-Lauguage?

As with all additions to the Language:

• 1) larger executables (especially unwanted, for libraries: .a, .dll/.so)

Actually that is a common misconception. Basically the most used listtypes are a handful of basetypes including pointer/reference.
Since all the pointer types (pointer to records/class etc) share implementation that only counts as one, same for all the 32-bit types etc.

Some bad compilers generate code a type that is semantically different but binary the same, but this often isn't needed. The .NET runtime brought this concept to the masses.

[St_W]

ps : St_W, I'm currently trying to go as fast as possible, hardest looks like behind me, stable & tested version planned within 2-3 months.

If you're just looking for a list implementation, you can find several of them here on the forums, btw. Yet, they are probably not tuned for fastest execution. I've written such List implementations too for some small projects. You can e.g. find stwList and stwMap as part of these little experiments: https://bitbucket.org/st_w/fb-wx/src/aa ... ?at=master and https://bitbucket.org/st_w/mmgc/src/5cf ... ?at=master

[jj2007]

A string character can not be compared to a list item (variable lenght)

Note that my demo deals with a 4MB string array, so in a way that is "variable length".

[Lost Zergling]

Just having a look at it ( stwList and stwMap ). Hard work here. Better technical level.
But some choices I decided to avoid. I still prefer my own approach.

[badidea]

Lists and trees are a great way to learn how to use pointers. Every time I need some list or tree class for a project, I write a new implementation. Because every time I think I can write nicer code or I just forgot that I implemented that list or tree before. Or I know I wrote it before, but wasn't unable to find it :-) And yes, there can be cache issues, but they just look so elegant.

[dodicat]

A string character can not be compared to a list item (variable lenght)

Note that my demo deals with a 4MB string array, so in a way that is "variable length".

Does this give the same results with your test file (Biblical thing)
(not the timings, the other stuff)

Code: Select all

#include "crt.bi"
#include "file.bi"
sub arraydelete(a() as string,char as string="")
    dim as long ctr=lbound(a)-1
    for n as long=lbound(a) to ubound(a)
        if instr(a(n),char)=0 then ctr+=1
        next
    redim as string b(ctr)
    ctr=lbound(a)-1
    for n as integer=lbound(a) to ubound(a)
        if instr(a(n),char)=0 then ctr+=1: b(ctr)=a(n)
        next n
        redim  a(lbound(b) to ubound(b))
        memcpy(@a(lbound(a)),@b(lbound(b)),(ubound(b)-lbound(b)+1)*sizeof(string))
        clear b(lbound(b)), 0, (ubound(b)-lbound(b)+1)*sizeof(string)
end sub

Function StringSplit(s_in As String,chars As String,result() As String) As Long
    Dim As Long ctr,ctr2,k,n,LC=len(chars)
    dim As boolean tally(Len(s_in))
    #macro check_instring()
        n=0
        while n<Lc
        If chars[n]=s_in[k] Then 
        tally(k)=true
        If (ctr2-1) Then ctr+=1
        ctr2=0
        exit while
        end if
        n+=1
       wend
    #endmacro
   
    #macro split()
    If tally(k) Then
        If (ctr2-1) Then ctr+=1:result(ctr)=Mid(s_in,k+2-ctr2,ctr2-1)
        ctr2=0
    End If
    #endmacro
    '==================  LOOP TWICE =======================
    For k  =0 To Len(s_in)-1
        ctr2+=1:check_instring()
    Next k
    If ctr Then Redim result(1 To ctr): ctr=0:ctr2=0 Else  Return 0
    For k  =0 To Len(s_in)-1
        ctr2+=1:split()
    Next k
    '===================== Last one ========================
    If ctr2>0 Then
        Redim Preserve result(1 To ctr+1)
        result(ctr+1)=Mid(s_in,k+1-ctr2,ctr2)
    End If
    Return Ubound(result)
End Function

Function loadfile(file as string) as String
	If FileExists(file)=0 Then Print file;" not found":Sleep:end
   var  f=freefile
    Open file For Binary Access Read As #f
    Dim As String text
    If Lof(1) > 0 Then
      text = String(Lof(f), 0)
      Get #f, , text
    End If
    Close #f
    return text
end Function



print filelen("testfile.txt"),"File length"
var g=loadfile("testfile.txt")
print len(g),"File length compare"


redim as string s()
dim as double t=timer
stringsplit(g," ",s())
print "Time to load into array ";(timer-t)
print ubound(s), "array size before"
t=timer
arraydelete(s(),"devil")
print "Time to delete devil ";(timer-t)
print ubound(s),"array size after"



sleep
 

[Lost Zergling]

Hi Dodicat,
I am not very comfortable with your programming style and I must admit that I have difficulties even reading it. I feel that this code could be very useful for reading files much more faster than line per line by working with blocks. In this case, it could be very usefull for me because I was looking for something like this written in Basic. If so I may have to rewrite a lot of algo (not in list but in array loading from files), so I'm not in hurry with this issue. I see it as a related proposition but I may be wrong.
ps : I had already tried something else in that mind (working 600 Mb by 600 Mb blocks using Get#) but I failed to improve the performance compared to the Line Input because transforming the string into an array was too resource consuming. Your solution deserves that one is interested. For non LF/CRLF files, I'm pretty sure I already may change my algo.