Re: [PATCH] [patch 4a/4] ipc: sem optimise simple operations

[Nick Piggin <npiggin@suse.de>]

On Fri, Aug 14, 2009 at 09:16:00PM +0200, Manfred Spraul wrote:
> An alternative patch to Nick's proposal:
> http://lkml.org/lkml/2009/8/11/11
> The patch is based on Nick's patch.
> 
> The patch is ontop of the first three patches from Nick.
> 
> Identical with Nick's patch:
> - per semaphore list to optimize single sop semop calls:
> This avoids that the semaphore operations have to scan through all waiting
> tasks, even for the tasks that are waiting on a different semaphore from
> the same array.
> 
> Differences:
> - same code for per-semaphore and global list.
> - one list for both wait-for-zero and decrement instead of two lists.
> - unlink_queue helper function
> 
> Open points:
> - further testing
> - understand all changes. e.g. why switch from "if (alter)" to
> 	"if (alter & !error)" in update_queue
> 
> >From the diffstat, it's simpler: 50 new lines instead of 110 new lines.
> 
> Nick: What do you think? Could you try your test app?

The problem with using the same algorithm is that we don't need to
"restart scanning" the simple-op lists when one of them succeeds.
This is because if a negative op fails, then no amount of subsequent
simple negative ops will make it succeed.

With multi-ops, it can be adding and subtracting and waiting for
zero of different sems etc, so in order to try to stay strictly
FIFO, then we always have to recheck all previous failed ops after
one succeeds.

The other problem is that we have to scan all ops in the multi-op
list because we don't know what combination of sem values might
allow the op to succeed. With the single-op lists, we know if the
semval is 0, then we don't have to scan the negative list, and if
it is non-0 then we don't have to scan the zero list.

Combine these two problems and that is where the O(n^2) behaviour
comes in to the complex-op algorithm.