Simplify ThreadData* management for a Bucket inside ParkingLot.cpp
Created attachment 284349 [details] Patch
This is not a regular patch but a kind of POC to see if I should spend more time in this direction. Currently, management of ThreadData* inside Bucket of HashTable in ParkingLot.cpp needs at least 3 pointers (As with any Singly LinkedList being used as Queue/FIFO): 1) queueHead 2) queueTail 3) nextInQueue and during dequeuing we need more pointers 4) currentPtr 5) previous At a given time, juggling with 5 pointers and ensuring each is pointing to correct location is error prone task (even though common for LinkedList) and probably hard to understand/maintain in future. If we don't worry about fairness of dequeue of enqueued threads aka we don't guarantee FIFO order, we could use a simple BitMap to keep track on equeued ThreadData* in Bucket (kind of simplified vector). We initially create BitMap of 32 size (size of uint32_t) which is expandable (or we could even start with smaller size is required). Size of this is capped by number of threads in system (and if unlucky, all thread waiting on same address in which case this BitMap size = number of threads) We create Array of ThreadData*, and BitMap entries indicate which entries in this Array is valid (BitMap is our gold reference) If BitMap entry is 0, that slot in Array is free. If BitMap entry for location is 1, that slot in Array is occupied by Valid ThreadData* entry. This made dequeue/enqueue logic very simple. equeue: Search for first 0 in BitMap and put ThreadData* in that slot dequeue : Search for first 1 in BitMap and clear that bit after extracting ThreadData* from it. (This also gets rid of clever abomination :-) which is common for LinkedList remove and not to mention hard to understand) Ignore Result: now does not do any manipulation to pointer. RemoveAndStop & RemoveAndContinue Result are now just clearing bit and moving on. This patch is just POC, so I have ignored efficiency and some good programming practices so please feel free to point them out. If most of the cases are where 1 thread has lock and another waiting for lock, FIFO probably does not add much, in which case BitMap approach is probably better as we don't need to keep track of any pointers. Thread Starvation is definitely possible in some scenario with this approach, such as Thread_1, and Thread_2 equeued, and then Thread_1 dequeued, and Thread_3 enqueued at first place (enqueue logic looks at first available slot by looking at first 0 bit) and then Thread_3 dequeued and Thread_4 enqueued at first place and so on and Thread_2 starves. In real world things are generally more random so above map not happen that often. IMO, If FIFO overhead is much more than BitMap, we could sacrifice FIFO for better code/efficiency. If FIFO is absolutely must during dequeue, this POC is DOA.
Comment on attachment 284349 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=284349&action=review I don't like this change. It makes the code more confusing, and I believe it's a regression since we want FIFO ordering. > Source/WTF/ChangeLog:32 > + If we don't worry about fairness of dequeue of enqueued threads > + aka we don't guranntee FIFO order, we could use a simple > + BitMap to keep track on equeued ThreadData* in Bucket > + (kind of simplied vector). I disagree, we want FIFO order.