[asterisk-bugs] [JIRA] (ASTERISK-26450) Change linkedlist to other list type

[Badalian Vyacheslav (JIRA)]

Badalian Vyacheslav created ASTERISK-26450:
----------------------------------------------

             Summary: Change linkedlist to other list type
                 Key: ASTERISK-26450
                 URL: https://issues.asterisk.org/jira/browse/ASTERISK-26450
             Project: Asterisk
          Issue Type: Improvement
      Security Level: None
            Reporter: Badalian Vyacheslav
            Severity: Critical


Plase replace linked list to other list type or change it!

Linked list have very poor perfomance becouse it can use vectorizaton! You try save memory but get poor perfomance and locking issues.

Variant 1 - You can replace next and prev fileds to INDEX and use Heap and get great perfomance. Also index and PTRs can be Atomic. If it's will be atomic you get LockFree Add, Delete, insert and Replace variant of list changes (Using atomic SWAP)!

Variant 2 - You can use sorted Heap and if you need insert in middle or other changes simple:
1. Create new Heap sized +X
2. Make 2 copy with BIG blockes (zones before insert and after insert) - VERY fast operation becouse new Processors can copy 1024 blocks in one Tick using SIMD.
3. Insert elem in new Heap
4. Change HEAD in HEAD struct to new address
5. Delete old Heap

If you use Head->Heap_addr[X]->Elem in all calls you have last version and non lock.
This varian also LockFree. Also its have Much less address becose you not have next fileds!

Small perfomace improvment also may be getted by commiler if use size_t,  uintptr_t and  ptrdiff_t.




--
This message was sent by Atlassian JIRA
(v6.2#6252)