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

[Nick Piggin <npiggin@suse.de>]

On Sun, Aug 16, 2009 at 01:29:23PM +0200, Manfred Spraul wrote:
> On 08/16/2009 12:31 PM, Nick Piggin wrote:
> >On Sat, Aug 15, 2009 at 06:32:14PM +0200, Manfred Spraul wrote:
> >   
> >>It depends. After disabling inlining, including all helper functions
> >>that differ:
> >>
> >>My proposal: 301 bytes for update_queue.
> >>
> >>"simple", only negv: 226 bytes
> >>"simple, negv+zero: 354 bytes
> >>simple+complex: 526 bytes.
> >>
> >>Thus with only +-1 simple ops, your version uses less icache. If both
> >>+-1 and 0 ops are used, your version uses more icache.
> >>     
> >Don't forget that in that case, your version is badly suboptimal
> >due to the algorithmic complexity.
> >   
> I know, I mentioned it in the change log:
> Waking up one "decrement by one" task is O(1) with your code and 
> O(1+<number of waiting-for-zero tasks>) with my code.
> 
> This is the price paid for saving memory:
> Your version keeps three pointers per semaphore (waiting-for-zero, 
> oldest decrement, newest decrement)
> My version keeps only two pointers (newest decrement, waiting-for-zero). 
> The "oldest decrement" is reconstructed on the fly, and that operation 
> is O(<number of waiting-for-zero tasks>).

OK, well let's just get something in.

I kind of liked to optimise both cases because it took this long to
uncover this suboptimal behaviour (and the problem isn't even
completely due to suboptimal semaphore but also userspace contention),
so even if there are some workloads with a little problem I don't know
if they will ever get reported/diagnosed.

That said, I'm not too unhappy with your version if you feel strongly
about it.

Thanks for reviewing the other patches too.