{"id":13109,"date":"2025-04-16T18:35:51","date_gmt":"2025-04-16T16:35:51","guid":{"rendered":"https:\/\/monodes.com\/predaelli\/?p=13109"},"modified":"2025-04-16T18:35:55","modified_gmt":"2025-04-16T16:35:55","slug":"1024cores-distributed-reader-writer-mutex","status":"publish","type":"post","link":"https:\/\/monodes.com\/predaelli\/2025\/04\/16\/1024cores-distributed-reader-writer-mutex\/","title":{"rendered":"1024cores – Distributed Reader-Writer Mutex"},"content":{"rendered":"\n

1024cores – Distributed Reader-Writer Mutex<\/a><\/em><\/p>\n\n\n\n

This is definitively something that I would like to Eiffelize!<\/p>\n\n\n\n\n\n\n\n\n\n\n\n

\n

Now, when we know that traditional reader-writer mutexes do no scale<\/a> and write sharing is our foe<\/a>, and that the way to go is state distribution<\/a>, let’s try to create a scalable distributed reader-writer mutex. The mutex is going to be very simple, I’m not going to dive too deep into advanced lockfree algorithms, let’s just create the simplest possible distributed design, and see what performance and scalability we will achieve.<\/p>\n\n\n\n

The mutex is based on per-processor data<\/a>, and it leads to a very simple implementation. If it would be based on per-thread data instead, we would need to cope with dynamic thread registration\/deregistration and properly synchronize arriving\/terminating readers with writers.<\/p>\n\n\n\n

The idea is very simple. We merely create a traditional reader-writer mutex per CPU; a reader acquires in shared mode a mutex it thinks refers to presumably current CPU; while a writer acquires in exclusive mode all the mutexes:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Note that it’s OK if a reader acquires a “wrong” mutex – they all are plain reader-writer mutexes in itself, so they support several concurrent readers. No additional synchronization between writers is required, writers acquire the mutexes in the same order (from 0 to P-1), so ownership over mutex 0 basically determines who is the “current” writer (all other potential writers are parked on mutex 0).<\/p>\n\n\n\n

As an underlying reader-writer mutex type I use plain pthread_rwlock_t; sched_getcpu() is used to obtain current processor number. Let’s move on to implementation. First, let’s define data structures:<\/p>\n\n\n\n

typedef struct distr_rw_mutex_cell_t<\/p>\n\n\n\n

{<\/p>\n\n\n\n

pthread_rwlock_t mtx;<\/p>\n\n\n\n

char pad [CACHE_LINE_SIZE – sizeof(pthread_rwlock_t)];<\/p>\n\n\n\n

} distr_rw_mutex_cell_t;<\/p>\n\n\n\n

typedef struct distr_rw_mutex_t<\/p>\n\n\n\n

{<\/p>\n\n\n\n

int proc_count;<\/p>\n\n\n\n

char pad [CACHE_LINE_SIZE – sizeof(int)];<\/p>\n\n\n\n

distr_rw_mutex_cell_t cell [0];<\/p>\n\n\n\n

} distr_rw_mutex_t;<\/p>\n\n\n\n

Constructor merely determines total number of processors in a system, memorizes it, and initializes per-processor mutexes. While destructor destroys the mutexes and frees memory:<\/p>\n\n\n\n

int distr_rw_mutex_create (distr_rw_mutex_t** mtx_p)<\/p>\n\n\n\n

{<\/p>\n\n\n\n

distr_rw_mutex_t* mtx;<\/p>\n\n\n\n

int proc_count;<\/p>\n\n\n\n

int i;<\/p>\n\n\n\n

proc_count = (int)sysconf(_SC_NPROCESSORS_CONF);<\/p>\n\n\n\n

if (posix_memalign((void**)&mtx, CACHE_LINE_SIZE,<\/p>\n\n\n\n

sizeof(distr_rw_mutex_t) +<\/p>\n\n\n\n

proc_count * sizeof(distr_rw_mutex_cell_t)))<\/p>\n\n\n\n

return 1;<\/p>\n\n\n\n

mtx->proc_count = proc_count;<\/p>\n\n\n\n

for (i = 0; i != proc_count; i += 1)<\/p>\n\n\n\n

{<\/p>\n\n\n\n

if (pthread_rwlock_init(&mtx->cell[i].mtx, 0))<\/p>\n\n\n\n

{<\/p>\n\n\n\n

while (i –> 0)<\/p>\n\n\n\n

pthread_rwlock_destroy(&mtx->cell[i].mtx);<\/p>\n\n\n\n

free(mtx);<\/p>\n\n\n\n

return 1;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

}<\/p>\n\n\n\n

*mtx_p = mtx;<\/p>\n\n\n\n

return 0;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

int distr_rw_mutex_destroy (distr_rw_mutex_t* mtx)<\/p>\n\n\n\n

{<\/p>\n\n\n\n

int i;<\/p>\n\n\n\n

for (i = 0; i != mtx->proc_count; i += 1)<\/p>\n\n\n\n

pthread_rwlock_destroy(&mtx->cell[i].mtx);<\/p>\n\n\n\n

free(mtx);<\/p>\n\n\n\n

return 0;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

Write lock\/unlock functions merely lock\/unlock all the mutexes. Not much to comment here:<\/p>\n\n\n\n

int distr_rw_mutex_wrlock (distr_rw_mutex_t* mtx)<\/p>\n\n\n\n

{<\/p>\n\n\n\n

int i;<\/p>\n\n\n\n

for (i = 0; i != mtx->proc_count; i += 1)<\/p>\n\n\n\n

pthread_rwlock_wrlock(&mtx->cell[i].mtx);<\/p>\n\n\n\n

return 0;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

int distr_rw_mutex_wrunlock (distr_rw_mutex_t* mtx)<\/p>\n\n\n\n

{<\/p>\n\n\n\n

int i;<\/p>\n\n\n\n

for (i = 0; i != mtx->proc_count; i += 1)<\/p>\n\n\n\n

pthread_rwlock_unlock(&mtx->cell[i].mtx);<\/p>\n\n\n\n

return 0;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

Read lock function obtains [approximation] of current processor, memorizes it, and locks in shared mode respective mutex. Read unlock function just unlocks the same mutex. Note that unlock function can’t re-obtain current processor number and use, it must use processor number obtained in the lock function (because processor might be changed):<\/p>\n\n\n\n

int distr_rw_mutex_rdlock (distr_rw_mutex_t* mtx, int* proc)<\/p>\n\n\n\n

{<\/p>\n\n\n\n

*proc = sched_getcpu();<\/p>\n\n\n\n

pthread_rwlock_rdlock(&mtx->cell[*proc].mtx);<\/p>\n\n\n\n

return 0;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

int distr_rw_mutex_rdunlock (distr_rw_mutex_t* mtx, int proc)<\/p>\n\n\n\n

{<\/p>\n\n\n\n

pthread_rwlock_unlock(&mtx->cell[proc].mtx);<\/p>\n\n\n\n

return 0;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

Performance<\/p>\n\n\n\n

In order to verify performance and scalability, I benchmarked the mutex against pthread_rwlock_t. The benchmark is very simple: 1 reader-writer mutex, an array of N int’s (the data) and P worker threads. Each worker thread constantly acquires the mutex in shared mode and verifies data’s consistency. Periodically each worker thread acquires the mutex in exclusive mode and mutates the data. The benchmark was executed on a 4 processor x 4 cores AMD machine (16 hardware threads in total) running Linux 2.6.29.<\/p>\n\n\n\n

In the first run I set N=4, and vary period of writing as 10, 50, 100, 500, 1000 and 10000<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

And below is the same graph but without lines for distributed(500, 1000 and 10000):<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

In the second run I set N=256, the same two graphs below:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n

So, what we see on the graphs? Our distributed mutex is somewhat (10-60%) slower in uncontended case (note that 60% slowdown refers to the extreme case of 10% write rate + basically no useful work). pthread_rwlock_t is completely non-scalable under load even on read-mostly workloads (however, we see a slight attempt to scale with N=256 on 2 threads). Our distributed mutex scales much better, under 1\/10000 write rate it exposes perfect linear scaling.<\/p>\n\n\n\n

Note that that fact that we are using current processor number for read acquisition is crucial, because performance-wise per-processor data is basically equal to per-thread data (a processor runs one thread at a time). I’ve also benchmarked a randomized variant of the distributed mutex (it uses per-thread random number generators to choose a mutex for read acquisition), and I’ve tried to create kind of the best conditions for it – I set data size N to 256 and increase number of underlying reader-writer mutexes 4-fold. The benchmark showed that it scales better than a centralized mutex, however still far from per-processor mutex (write rate is presented in brackets):<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

The bottom line is that the implementation is very simple and comprehensible, performance is somewhat worse than pthread_rwlock_t, while scalability is significantly improved. The mutex can be used whenever you have high read load and low write-to-read ratio (~<1-5%).<\/p>\n\n\n\n

You can download the implementation along with the benchmark below (gcc\/Linux).<\/p>\n\n\n\n

<\/a><\/p>\n\n\n\n

https:\/\/drive.google.com\/embeddedfolderview?id=16Du4plUk3iBZJzNiP1JYnmjNMmufc0ff#list<\/a><\/p>\n\n\n\n

If not stated otherwise, all non-source-code text and images on this site are provided under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License<\/a>. Source code is covered by the Simplified BSD License<\/a> and by Apache License, Version 2.0<\/a>. The opinions expressed on this site are my own and do not necessarily reflect the views of Google.<\/p>\n<\/blockquote>\n\n\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

1024cores – Distributed Reader-Writer Mutex This is definitively something that I would like to Eiffelize!<\/p>\n

Read more →<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"federated","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[238,34,98],"tags":[],"class_list":["post-13109","post","type-post","status-publish","format-standard","hentry","category-agenda","category-eiffel","category-liberty-eiffel"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6daft-3pr","jetpack-related-posts":[{"id":9687,"url":"https:\/\/monodes.com\/predaelli\/2022\/10\/01\/spacevim-has-eiffel-support\/","url_meta":{"origin":13109,"position":0},"title":"SpaceVim has Eiffel support!","author":"Paolo Redaelli","date":"2022-10-01","format":false,"excerpt":"SpaceVim, a community-driven vim distribution that seeks to provide layer feature, besides turning Vim into a nifty IDE for several languages (C\/C++, Rust, Kotlin, Go, Python, Java and JavaScript plus others), it offers among the available layers one for Eiffel! \u00a0","rel":"","context":"In "Eiffel"","block_context":{"text":"Eiffel","link":"https:\/\/monodes.com\/predaelli\/category\/eiffel\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":5808,"url":"https:\/\/monodes.com\/predaelli\/2019\/06\/28\/5808\/","url_meta":{"origin":13109,"position":1},"title":"https:\/\/twitter.com\/wvo\/status\/1144331578006335488?s=20 Single header C++ WASM\u2026","author":"Paolo Redaelli","date":"2019-06-28","format":false,"excerpt":"https:\/\/twitter.com\/wvo\/status\/1144331578006335488?s=20 Single header C++ WASM binary writer (with linking\/reloc support): (link: https:\/\/github.com\/aardappel\/lobster\/blob\/master\/dev\/src\/lobster\/wasm_binary_writer.h) github.com\/aardappel\/lobs\u2026 as part of the Lobster WASM backend: (link: http:\/\/aardappel.github.io\/lobster\/implementation_wasm.html) aardappel.github.io\/lobster Time is ripe to start implementing an LLVM Liberty Eiffel backend. For real, this time \ud83d\ude03","rel":"","context":"In "Eiffel"","block_context":{"text":"Eiffel","link":"https:\/\/monodes.com\/predaelli\/category\/eiffel\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1286,"url":"https:\/\/monodes.com\/predaelli\/2016\/04\/17\/eiffel-a-viable-candidate-as-a-language-for-the-gnome-platform\/","url_meta":{"origin":13109,"position":2},"title":"Eiffel: A viable candidate as a language for the Gnome platform ?","author":"Paolo Redaelli","date":"2016-04-17","format":false,"excerpt":"Eiffel: A viable candidate as a language for the Gnome platform ? It was 2004. Linux were labelled as a cancer by Ballmer, Android and iPhone didn't existed. Multi-core CPU were still high-end. It was a different world. From archive.org, before it got lost.... Twelve years ago. And it was\u2026","rel":"","context":"In "Eiffel"","block_context":{"text":"Eiffel","link":"https:\/\/monodes.com\/predaelli\/category\/eiffel\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4776,"url":"https:\/\/monodes.com\/predaelli\/2018\/10\/24\/ecma-eiffel-syntax-guide\/","url_meta":{"origin":13109,"position":3},"title":"(ECMA) Eiffel Syntax Guide","author":"Paolo Redaelli","date":"2018-10-24","format":false,"excerpt":"(ECMA) Eiffel Syntax Guide","rel":"","context":"In "Eiffel"","block_context":{"text":"Eiffel","link":"https:\/\/monodes.com\/predaelli\/category\/eiffel\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":9332,"url":"https:\/\/monodes.com\/predaelli\/2022\/05\/01\/liberty-liberty-eiffel-programming-language\/","url_meta":{"origin":13109,"position":4},"title":"Liberty | Liberty Eiffel programming language","author":"Paolo Redaelli","date":"2022-05-01","format":false,"excerpt":"Liberty Source: Liberty | Liberty Eiffel programming language","rel":"","context":"In "Liberty Eiffel"","block_context":{"text":"Liberty Eiffel","link":"https:\/\/monodes.com\/predaelli\/category\/eiffel\/liberty-eiffel\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":11120,"url":"https:\/\/monodes.com\/predaelli\/2024\/01\/07\/yet-another-missing-eiffel-%f0%9f%98%a2\/","url_meta":{"origin":13109,"position":5},"title":"Yet another missing Eiffel \ud83d\ude22","author":"Paolo Redaelli","date":"2024-01-07","format":false,"excerpt":"On https:\/\/github.com\/attractivechaos\/plb2 there is yet another programming language benchmark. And yet another not having Eiffel.... In addition to C, there is Nim, V, Rust.... that's very sad \ud83d\ude22","rel":"","context":"In "Eiffel"","block_context":{"text":"Eiffel","link":"https:\/\/monodes.com\/predaelli\/category\/eiffel\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/posts\/13109","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/comments?post=13109"}],"version-history":[{"count":0,"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/posts\/13109\/revisions"}],"wp:attachment":[{"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/media?parent=13109"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/categories?post=13109"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/monodes.com\/predaelli\/wp-json\/wp\/v2\/tags?post=13109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}