[Home]

Summary:ASTERISK-26450: core: Change linked list to other list type
Reporter:Badalian Vyacheslav (slavon)Labels:
Date Opened:2016-10-09 10:31:03Date Closed:2020-01-14 11:13:28.000-0600
Priority:MinorRegression?
Status:Closed/CompleteComponents:Core/General
Versions:Frequency of
Occurrence
Related
Issues:
Environment:Attachments:
Description:Plase replace linked list to other list type or change it!

Linked list have very poor perfomance becouse it can not use vectorizaton optimizations! 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.
Comments:By: Asterisk Team (asteriskteam) 2016-10-09 10:31:03.687-0500

Thanks for creating a report! The issue has entered the triage process. That means the issue will wait in this status until a Bug Marshal has an opportunity to review the issue. Once the issue has been reviewed you will receive comments regarding the next steps towards resolution.

A good first step is for you to review the [Asterisk Issue Guidelines|https://wiki.asterisk.org/wiki/display/AST/Asterisk+Issue+Guidelines] if you haven't already. The guidelines detail what is expected from an Asterisk issue report.

Then, if you are submitting a patch, please review the [Patch Contribution Process|https://wiki.asterisk.org/wiki/display/AST/Patch+Contribution+Process].
By: Joshua C. Colp (jcolp) 2016-10-09 10:37:46.384-0500

Do you plan on providing a patch and performance data for this? If not this would be considered a feature request. You can try to elicit some interest on the asterisk-dev mailing list from others to look into it.
By: Badalian Vyacheslav (slavon) 2016-10-09 10:49:09.425-0500

I can try provide patch but i think it's will be dirty (prototype) and will need to help for cleaning it..
But this also will have some features like Batched operations like
findall('value')->foreach()->{
// some actions in SIMD
}

Can i use OpenMP extesions in code?
You plain to add it support?

OpenMP intresting for SIMD and OpenCL, not for threading....

By: Joshua C. Colp (jcolp) 2016-10-09 10:59:39.532-0500

I know of noone currently working on OpenMP extensions or anything in this area for Asterisk.
By: Corey Farrell (coreyfarrell) 2016-10-09 15:00:51.202-0500

I suggest starting small with any effort like this.  A proof of concept that can show a reduction of overhead or simpler code by converting a single structure from linked list to vector.

For existing vector code within asterisk, check out {{include/asterisk/vector.h}}.  I don't know much about OpenMP but it's not currently used by Asterisk.  In Linux OpenMP is provided by libgomp which is GPLv3 (not LGPL).  I'm not sure this can be a "required" dependency (would pose a problem for non-GPL modules).  If OpenMP were optional you'd see less resistance to including it.
By: Badalian Vyacheslav (slavon) 2016-10-09 18:49:51.114-0500

Yes! Vector would fit great. Only there is not enough functions for clean replacements such as

AST_LIST_TRAVERSE
AST_LIST_INSERT_TAIL
AST_LIST_INSERT_HEAD
AST_LIST_INSERT_BEFORE_CURRENT

Now such a problem that in high quantities in WebRTC all AMI Events requests normally come and PeerStatus comes with a delay of 2-5 seconds. The machine is not loaded. Generally fighting is now in line with the transition to 200 concurrent calls. Number of peers with the 1000 online, while only about 5 thousand
By: Joshua C. Colp (jcolp) 2016-10-09 19:42:18.104-0500

I'd also suggest you do profiling to determine where most of the time is spent if you have not already.
By: Asterisk Team (asteriskteam) 2016-10-24 12:00:00.694-0500

Suspended due to lack of activity. This issue will be automatically re-opened if the reporter posts a comment. If you are not the reporter and would like this re-opened please create a new issue instead. If the new issue is related to this one a link will be created during the triage process. Further information on issue tracker usage can be found in the Asterisk Issue Guidlines [1].

[1] https://wiki.asterisk.org/wiki/display/AST/Asterisk+Issue+Guidelines