Bug 160088 – Simplify ThreadData* management for a Bucket inside ParkingLot.cpp

• Component: Web Template Framework
• Status: NEW

[Rajeev Misra]

Simplify ThreadData* management for a Bucket inside ParkingLot.cpp

[Rajeev Misra]

Created attachment 284349 [details]
Patch

[Rajeev Misra]

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.

[Filip Pizlo]

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.