PureBasic Forums - English

Restored from previous forum. Originally posted by tranquil.

Howdy ho all!

Our application is nearly completed (File Sharing) and is able to release next weeks but before that I want to be sure that our server runs as stable and fast as possible.

Atm its only possible to share 1000 Files per User which mades 60.000 Users maximal possible on a 512 MB System if I use arrays.

there are some advantages of arrays becouse I use it:
- Easylie threads can be used
- I do not need to browse through the whoule linked list if a user connects for deleting his shared-files

I would like to use linked lists for these purpose and do all search-requests on the serverside in the mainloop. (atm its threaded) But then I'm frightened that the network becomes very slow due to a fact that the server is working on search through the linked lists.

Does anyone have an example how to deal with threads and linked-lists? > threads should be have access to one list. But what is the best way to do it? Any Ideas?

Cheers
Mike

Tranquilizer/ Secretly!
http://www.secretly.de
Registred PureBasic User
System: Windows 2000 Server, 512 MB Ram, GeForce4200 TI 128 MB DDR, Hercules Theater 6.1 DTS Sound
System 2: Mobile Pentium 4 2.4GHz 512 MB DDR GeForce4 420-32, Windows XP Home

Restored from previous forum. Originally posted by freak.

Ok, here's my way...

For reading the List, it can be done in more threads at a time, the way i show below. But for those Parts of your Code that need to modify the List, it has to be done in a slower way.

For write acces, do the following:
You can do all changes using the usual List commands.

Now for the (faster) Readonly access... This code is similar to something like:

ResetList()
While NextElemtnt()
;
Wend

but it doesn't change anything (like the real NextElemnt() does, that changes the List position). This way more that one thread can Read the List at one Time, without any problems.

Anyway, while changing the List, there should also be no Thread reading an Entry, as this one can be deleeted in the same moment.
So you should also check for that.

Hope this helps...

Timo

Restored from previous forum. Originally posted by tinman.

Originally posted by freak

; when accessing:
While ListUsed: Wend ; wait for List to note be used.

It is still possible to get problems with multiple accesses here. The code will be compiled to something like this:
As you can see, if your thread gets interrupted after the CMP instruction (after setting the flag to escape the loop) and the next thread that runs also manages to perform that instruction, then you will have two threads which think they "own" the list.

Yes, it is a minute chance, but you know what Murphy's law states

The only clean way is to use the OS mechanisms for semaphores. They are fairly easy to use to achieve what you show (something like 4 function calls in total). Of course, the cleanest way would be to use PureBasic commands, but Fred did not provide methods for thread synchronisation or messaging (there must be to be able to fully use threads... Fred? .

You may also find the problem that while you can have many threads reading a list, you have not provided any means to lock the list against writes. It is not only multiple writes that should be avoided, but writes while there are any readers. You will need another semaphore type mechanism for that.

Code: Select all

; after first Element was added to the List:
ListStart = @MyList()

; now, when reading the contents:
*ListEntry.MyType = ListStart  ; where MYTipeis the Structure name of your List
Repeat
  *ListEntry = NextElementX(*ListEntry)

There will also be a problem here since you will never process the first item in the list. When you do @list() on an empty list you will get the result 8. So if you do it on a list with one item, you will get a pointer to the item. However, your example code moves onto the next item before doing any work with it. Better to use a While loop rather than a Repeat loop.


--
It's not minimalist - I'm increasing efficiency by reducing input effort.
(Win98first ed. + all updates, PB3.50)

Restored from previous forum. Originally posted by El_Choni.

As you can see, if your thread gets interrupted after the CMP instruction (after setting the flag to escape the loop) and the next thread that runs also manages to perform that instruction, then you will have two threads which think they "own" the list.

This code avoids that, and is faster than using API (tested):
Bye,

El_Choni

Restored from previous forum. Originally posted by tranquil.

@Freak:

I think I like your read-only methode. I will do some test these days and then I possible use this on serverside. Many thanks!!

Anyway, thanks again El_Choni and tinman!!

Greetz!

Mike

Tranquilizer/ Secretly!
http://www.secretly.de
Registred PureBasic User
System: Windows 2000 Server, 512 MB Ram, GeForce4200 TI 128 MB DDR, Hercules Theater 6.1 DTS Sound
System 2: Mobile Pentium 4 2.4GHz 512 MB DDR GeForce4 420-32, Windows XP Home

Restored from previous forum. Originally posted by freak.

> It is still possible to get problems with multiple accesses here.

I didn't know that, thanks for the Info.

> It is not only multiple writes that should be avoided, but writes while there are any readers.

That's why I said that there must be a check added for that (at the end of my post).

> There will also be a problem here since you will never process the first item in the list.

Sorry, i overlooked that. The Source here was not from one of my projects, I wrote it, just to make clear, how I would do it.

It was mainly to show, that you can read a List, without the LinkedList commands, which is useful here.

Anyway, thanks for pointimg my errors out

Timo

Restored from previous forum. Originally posted by tinman.

Originally posted by freak

> It is not only multiple writes that should be avoided, but writes while there are any readers.

That's why I said that there must be a check added for that (at the end of my post).

Oops, sorry. I missed that

@El_Choni:
Nice. How much faster than the OS is it? Also, I noticed the IA32 reference manual say that "this instruction can be used with a LOCK prefix to allow the instruction to be executed atomically" - any idea what this lock prefix is, since you would need that to make your snippet work correctly. (Sorry if that's a stupid question but IA32 is new to me.)



--
It's not minimalist - I'm increasing efficiency by reducing input effort.
(Win98first ed. + all updates, PB3.51)

Restored from previous forum. Originally posted by El_Choni.

@tinman: you're right, I forgot the lock prefix, which in fact the trick to make this work. Also I think test eax, eax won't be needed. Sorry, I pasted it from memory (my own).

Thanks for pointing it out. Bye,

El_Choni

Restored from previous forum. Originally posted by tranquil.

Hi all. Back again.

I made some tests with very intresting results with dimensions and linked lists. I allways thought that linked lists are much faster and do not need as lot as memory a dimension need. that seems to be wrong.

Done the following tests with our server-applicatin:

hosting 40.000 User where each user is sharing 1000 Files and browsing through it once gives following results:

40.000 x 1.000 dimensions needs 180019 ticks and nearly 300 MB of free memory

same for elements needs more then my available memory and takes MUCH MUCH more time so that I must aborted the test.

So I will choose the array version now.

If anyone want I can paste a small testsource here where everyone can try it himselfe who do not believe. )

Mike

Tranquilizer/ Secretly!
http://www.secretly.de
Registred PureBasic User
System: Windows 2000 Server, 512 MB Ram, GeForce4200 TI 128 MB DDR, Hercules Theater 6.1 DTS Sound
System 2: Mobile Pentium 4 2.4GHz 512 MB DDR GeForce4 420-32, Windows XP Home

Restored from previous forum. Originally posted by Pupil.

Everyone that know something about linked lists and how they're build could have told you that they're slower and takes more memory/item than an array. This is how an element in a linked list look like, as you can se it takes 8 bytes/element extra compared to an array: About the speed difference:
If you want to look at a specified item in an array or linked list you will see that to get the memory address of that particular item in an array is just a mather of math, but for the linked list you have to iterate through the elements to get to the same item. So you get the item in an array with less than 10 assembly operations but, depending on how deep the item is into the list, you maybe have to execute 1000 assembly operations before getting to the right element in a linked list.

This is the price you have to pay for the flexibility that linked list gives you, there are ways to speed up the linked list some but these methods and their usefullness depends on how your program wants to access and use the linked lists.