8 replaced http://programmers.stackexchange.com/ with https://softwareengineering.stackexchange.com/
source | link

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46. I found an independent [re]implementation of Michael's algorithm at http://people.cs.vt.edu/~scschnei/streamflow/

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 4 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46. I found an independent [re]implementation of Michael's algorithm at http://people.cs.vt.edu/~scschnei/streamflow/

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 4 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46. I found an independent [re]implementation of Michael's algorithm at http://people.cs.vt.edu/~scschnei/streamflow/

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 4 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

    Post Closed as "Opinion-based" by gbjbaanb, Bart van Ingen Schenau, AProgrammer, user40980, gnat
7 added 114 characters in body
source | link

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46. I found an independent [re]implementation of Michael's algorithm at http://people.cs.vt.edu/~scschnei/streamflow/

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 34 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46.

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 3 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46. I found an independent [re]implementation of Michael's algorithm at http://people.cs.vt.edu/~scschnei/streamflow/

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 4 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

6 another paper, this one with implementation available
source | link

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46.

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 3 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46.

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

As a footnote, I see there are 3 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.

Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).

For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is "slightly better than [Google's] tcmalloc" on up to 64-cores. Another interesting point in that paper is that "llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap)". jemalloc and ptmalloc are also benchmarked in there.

References:

[1] Michael, Maged M. "Scalable lock-free dynamic memory allocation." ACM Sigplan Notices 39.6 (2004): 35-46.

[2] Huang, Xiaohuang, et al. "Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines." Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.

[3] Kukanov, Alexey, and Michael J. Voss. "The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks." Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the "S13" suffix in the course name.

[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. "NBmalloc: Allocating memory in a lock-free manner." Algorithmica 58.2 (2010): 304-338. Source code available for this one.

As a footnote, I see there are 3 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.

5 added 53 characters in body
source | link
4 added 53 characters in body
source | link
3 added 68 characters in body
source | link
2 added 439 characters in body
source | link
1
source | link