STM implementation

STM implementation

[Yubin Ruan]

Hi Paul,

I writing to ask about implementation of STM (software transactional memory).

I just finish section 17 of the perfbook, but that doesn't say much about
implementations of transactional memory, especially STM. Basically I
understand the common implementation of HTM (hardware transactional memory)
and have experience using it (thanks to the meltdown paper[1] and the original
HTM paper[2] and some other materials[3]). But I cannot find useful materials
on the topic of STM implementation. I read through the original STM paper[4],
but found it a bit cryptographic (hard to understand). Based on the materials
I read so far, STM can be implemented using lock-free algorithms or simply
locking. Alternatively, it can also be implemented using techniques similar to
those in the database world (write-ahead logging, i.e., journaling). But I
guess a robust and efficient implementation will require more to handle issues
such as I/O ? Can you provide some hints on this topic?

I am still investigating and will really appreciate any comments.

        Yubin

[1]: https://meltdownattack.com/meltdown.pdf
    (The meltdown paper)

[2]: http://cs.brown.edu/~mph/HerlihyM93/herlihy93transactional.pdf
    (Transactional Memory: Architectural Support for Lock-Free Data Structures)

[3]: https://www.scss.tcd.ie/~jones/CS4021/transactional%20memory.pdf
    (A lecture note on Intel TSX, which also talk about implementation of HTM)

[4]: https://pdfs.semanticscholar.org/846e/87f6c8b9d8909d678b5c668cfe46cf40a348.pdf
    (Software Transactional Memory)

Re: STM implementation

[Paul E. McKenney]

On Mon, Jan 15, 2018 at 10:28:33PM +0800, Yubin Ruan wrote:
> Hi Paul,
> 
> I writing to ask about implementation of STM (software transactional memory).
> 
> I just finish section 17 of the perfbook, but that doesn't say much about
> implementations of transactional memory, especially STM. Basically I
> understand the common implementation of HTM (hardware transactional memory)
> and have experience using it (thanks to the meltdown paper[1] and the original
> HTM paper[2] and some other materials[3]). But I cannot find useful materials
> on the topic of STM implementation. I read through the original STM paper[4],
> but found it a bit cryptographic (hard to understand). Based on the materials
> I read so far, STM can be implemented using lock-free algorithms or simply
> locking. Alternatively, it can also be implemented using techniques similar to
> those in the database world (write-ahead logging, i.e., journaling). But I
> guess a robust and efficient implementation will require more to handle issues
> such as I/O ? Can you provide some hints on this topic?
> 
> I am still investigating and will really appreciate any comments.

Hello, Yubin,

There has been a huge variety of STM implementations over the years.
Last I looked into it carefully (admittedly some years back), there was
a tradeoff between performance and scalability, but both performance
and scalability were quite poor compared to non-TM approaches.

A colleague of mine had good things to say about SwissTM, but that was
more than five years ago.  Michael Spear has done quite a bit of more
recent STM work, so looking at his publications would be helpful.

Please let me know how it goes!

							Thanx, Paul

>         Yubin
> 
> [1]: https://meltdownattack.com/meltdown.pdf
>     (The meltdown paper)
> 
> [2]: http://cs.brown.edu/~mph/HerlihyM93/herlihy93transactional.pdf
>     (Transactional Memory: Architectural Support for Lock-Free Data Structures)
> 
> [3]: https://www.scss.tcd.ie/~jones/CS4021/transactional%20memory.pdf
>     (A lecture note on Intel TSX, which also talk about implementation of HTM)
> 
> [4]: https://pdfs.semanticscholar.org/846e/87f6c8b9d8909d678b5c668cfe46cf40a348.pdf
>     (Software Transactional Memory)
>