Leyne, Sean wrote:

> The follow link presents efficient Lock Algorithm for Shared Objects in SMP Environments, interesting stuff for Firebird 3.0 perhaps ?
>
> http://sciencelinks.jp/j-east/article/200701/000020070106A1030952.php
>
> <SL> Here is the URL for the actual paper http://www.jstage.jst.go.jp/article/ipsjdc/2/0/759/_pdf
>
> <SL> While not being a low level programmer, I think that the usefulness of the algorithm may be limited due to issues noted in section 6.2 of the paper:
>
> "...Our algorithm does not rely on memory ordering between lock and non-locking operations, though it does rely on the memory ordering within the lock operation.
>
> Existing memory ordering models, such as acquire and release, do not support memory ordering that the algorithm requests, or the ordering of a specific store or specific load...
>
> Therefore, compilers should schedule these instructions to avoid such penalties ... to evade unnecessary stall cycles..."
>
> <SL> This suggests that the implementation of the algorithm within Firebird would require changes to compilers, which are outside of the Firebird's control.
>
>

Sean, I think you'll find that Intel and AMD x86 and Sparc support
program order memory writes, and are presumably OK for this scheme.
Alpha and Itanium (aka Itanic) are definitely not. Also, tagging the
required variables would need to be marked volatile, so it is most
unlikely that any compiler would/could generate code containing branches
out of order. So the scheme is probably safe for the purpose intended.

That said, the scheme is designed for exclusive locks only and has no
form of deadlock detection, so it couldn't be used for the Firebird lock
manager, exception, perhaps, in lieu of a the mutex on the lock manager
itself.

However, I think the analysis presented is seriously flawed, as are the
measured performance gains. Much of the cost of an interlocked
instruction is the need to to flush cached memory writes to preserve
memory ordering with regard to the interlocked instruction. The same
flushing is required when one core tries to read + write a memory
location marked as dirty in another processor's cache. No matter how
the contention occurs, the architectural memory write order must be
preserved.

What I think what the author's measured was the god-awful implementation
of interlocked instructions on Xeons before Intel noticed that AMD was
vastly outperforming Intel on SMP. Intel may be lazy, but it isn't
stupid, and did both a short term and a long term fix to their memory
architecture. The processors Intel has been shipping for the last
couple of years are competitive with AMD on interlocked instructions,
and their Nehalem family are probably superior.

I'm not at all sure that this technology is suitable for a Firebird lock
manager,
but there's probably enough there to be worth serious study.

--
Jim Starkey
Sent from Shearwater, off
the coast of New England