Tuesday, November 27, 2018

Digest for comp.lang.c++@googlegroups.com - 7 updates in 4 topics

Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Nov 27 11:27PM

\o/ Just implemented transitions; video is of applying an easing function
to a widget property (widget position) ..
https://www.youtube.com/watch?v=7UZTGqskPuI #cpp #coding #gamedev
 
/Flibble
 
--
"You won't burn in hell. But be nice anyway." – Ricky Gervais
 
"I see Atheists are fighting and killing each other again, over who
doesn't believe in any God the most. Oh, no..wait.. that never happens." –
Ricky Gervais
 
"Suppose it's all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I'd say, bone cancer in children? What's that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It's not right, it's utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That's what I would say."
Elephant Man <conanospamic@gmail.com>: Nov 27 09:12PM

Article d'annulation posté via Nemo.
"Öö Tiib" <ootiib@hot.ee>: Nov 27 08:28AM -0800

> "g++ -std=c++17 t.cpp" works well, I forgot the standard option for g++.
> But the standard I am after is c++11. "g++ -std=c++11 t.cpp" causes the
> same linker error! I can not understand why.
 
If you want to use C++11 then you should not use C++17 features.
You have to define the Token::Pi in C++11. Adding that to end of
your file ...:
 
constexpr Str Token::Pi;
 
... will make it to compilöe with -std=c++11 too.
 
If you want to learn to use constexpr then I would suggest to forget
C++11. The constexpr as of C++11 is rather limited and crippled,
especially about functions. There it feels like a hack to simplify
some of most obscure template metaprogramming tricks and
for some performance optimizations.
 
The constexpr of C++17 on the other hand feels like a way to
mark pure functions (in functional programming sense) with keyword
constexpr. Preferring pureness is quite good programming idiom
in general, about like preferring immutability is good programming
idiom in general.
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Nov 26 09:59PM -0800

On 11/25/2018 10:19 PM, Chris M. Thomasson wrote:
> pointers into a table of locks. A thread can create a little array of
> hashed pointers, sort them, remove duplicates, then take all of the
> locks in the table. The sorting and uniqueness factor prevents deadlock.
[...]
 
Hey now, this crude example code actually uses threads. ;^)
 
Deadlock free hashed address based locking, dead simple wrt a locking
hierarchy. It can be improved upon for sure. I am calling it the Multex.
 
Also, keep in mind that the locks are different than the memory pointed
to by the hashed pointers. So, this can be used to simulate atomic
operations on a system that only has semaphores. It easily solves the
Dining Philosophers problem.
 
The main and ct_thread functions show an example on how to use it:
____________________________
/*
The Multex, simple deadlock free locking abstraction
By Chris M. Thomasson
____________________________________________________________*/
 
 
#include <iostream>
#include <functional>
#include <algorithm>
#include <mutex>
#include <thread>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
 
 
#define THREADS 7
#define N 123456
 
 
// Allows one to lock multiple addresses
// at once, and never hit a deadlock.
// It is an experiment.
namespace ct_multex
{
// A table of locks
struct mutex_table
{
std::vector<std::mutex> m_locks;
 
mutex_table(std::size_t size) : m_locks(size) { assert(size > 0); }
 
// totally contrived simple hash...
std::size_t hash(void const* ptr)
{
std::uintptr_t ptr_uint = (std::uintptr_t)ptr;
return (std::size_t)(((ptr_uint << 9) * 103) % m_locks.size());
}
};
 
// A threads local indices into a table of locks
struct local_locks
{
std::vector<std::size_t> m_lock_idxs;
mutex_table& m_mtx_tbl;
 
local_locks(mutex_table& mtx_tbl) :
m_lock_idxs(), m_mtx_tbl(mtx_tbl) {}
 
// Add an address to be locked
void push_ptr(void const* ptr)
{
std::size_t idx = m_mtx_tbl.hash(ptr);
m_lock_idxs.push_back(idx);
}
 
// Deadlock free, baby! ;^)
void ensure_locking_order()
{
// sort and remove duplicates...
std::sort(m_lock_idxs.begin(), m_lock_idxs.end());
m_lock_idxs.erase(std::unique(m_lock_idxs.begin(),
m_lock_idxs.end()), m_lock_idxs.end());
}
 
// Take all of the locks
void lock()
{
// there can be a flag to minimize this...
ensure_locking_order();
 
std::size_t n = m_lock_idxs.size();
 
for (std::size_t i = 0; i < n; ++i)
{
m_mtx_tbl.m_locks[m_lock_idxs[i]].lock();
}
}
 
// Unlock everything
void unlock()
{
std::size_t n = m_lock_idxs.size();
 
for (std::size_t i = 0; i < n; ++i)
{
m_mtx_tbl.m_locks[m_lock_idxs[n - i - 1]].unlock();
}
}
};
 
 
// RAII scoped lock: Allows a thread to actualy take the locks
// It locks a threads local lock indices
struct scoped_lock
{
local_locks& m_locks;
 
scoped_lock(local_locks& locks) : m_locks(locks)
{
m_locks.lock();
}
 
~scoped_lock() throw()
{
m_locks.unlock();
}
};
}
 
 
 
 
// Test program...
//______________________________________
 
// Shared data
struct ct_shared
{
ct_multex::mutex_table& m_multex;
 
ct_shared(ct_multex::mutex_table& multex)
: m_multex(multex), data_0(1), data_1(2), data_2(3), data_3(4) { }
 
unsigned long data_0;
unsigned long data_1;
unsigned long data_2;
unsigned long data_3;
};
 
 
 
// a thread
void ct_thread(ct_shared& shared)
{
// Create our local locks
ct_multex::local_locks locks(shared.m_multex);
 
// Add some addresses
locks.push_ptr(&shared.data_2);
locks.push_ptr(&shared.data_0);
 
// Do some work
for (unsigned long i = 0; i < N / 2; ++i)
{
{
ct_multex::scoped_lock slock(locks);
// locked for data_0 and data_2
shared.data_0 += i;
shared.data_2 += i;
}
 
std::this_thread::yield();
 
{
ct_multex::scoped_lock slock(locks);
// locked for data_0 and data_2
shared.data_0 -= i;
std::this_thread::yield(); // for fun...
shared.data_2 -= i;
}
}
 
// Add some other addresses
locks.push_ptr(&shared.data_1);
locks.push_ptr(&shared.data_3);
 
// Do some more work...
for (unsigned long i = 0; i < N / 2; ++i)
{
{
ct_multex::scoped_lock slock(locks);
// locked for data_0, data_1, data_2 and data_3
shared.data_0 += i;
std::this_thread::yield(); // for fun...
shared.data_1 += i;
shared.data_2 += i;
shared.data_3 += i;
}
 
std::this_thread::yield();
 
{
ct_multex::scoped_lock slock(locks);
// locked for data_0, data_1, data_2 and data_3
shared.data_0 -= i;
shared.data_1 -= i;
shared.data_2 -= i;
std::this_thread::yield(); // for fun...
shared.data_3 -= i;
}
}
}
 
 
int main(void)
{
{
// Our mutex table
ct_multex::mutex_table multex_tbl(42);
 
// Our shared data
ct_shared shared(multex_tbl);
 
// Launch...
{
std::thread threads[THREADS];
 
// Create threads...
for (unsigned long i = 0; i < THREADS; ++i)
{
threads[i] = std::thread(ct_thread, std::ref(shared));
}
 
std::cout << "processing...\n\n";
std::cout.flush();
 
// Join threads...
for (unsigned long i = 0; i < THREADS; ++i)
{
threads[i].join();
}
}
 
// Verify the shared data...
std::cout << "shared.data_0 = " << shared.data_0 << "\n";
std::cout << "shared.data_1 = " << shared.data_1 << "\n";
std::cout << "shared.data_2 = " << shared.data_2 << "\n";
std::cout << "shared.data_3 = " << shared.data_3 << "\n";
 
assert(shared.data_0 == 1);
assert(shared.data_1 == 2);
assert(shared.data_2 == 3);
assert(shared.data_3 == 4);
}
 
std::cout << "\n\nfin!\n\n";
 
return 0;
}
____________________________
 
 
Can you get it to run?
 
thanks.
Melzzzzz <Melzzzzz@zzzzz.com>: Nov 27 07:24AM

> Can you get it to run?
 
> thanks.
~/News >>> g++ -std=c++17 -O3 -march=native -pthread mmtex.cpp -o mmtex 2> errors
~/News >>> vim errors
~/News >>> ./mmtex
processing...
 
shared.data_0 = 1
shared.data_1 = 2
shared.data_2 = 3
shared.data_3 = 4
 
 
fin!
 
 
--
press any key to continue or any other to quit...
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Nov 26 11:25PM -0800

On 11/26/2018 9:59 PM, Chris M. Thomasson wrote:
> // It is an experiment.
> namespace ct_multex
> {
[...]
>                 m_mtx_tbl.m_locks[m_lock_idxs[i]].lock();
>             }
>         }
[...]
 
Fwiw, there is another way to take the locks, using a try_lock and
backoff scheme, something like:
_____________________________
// Take all of the locks
void lock() // optimistic
{
// there can be a flag to minimize this...
ensure_locking_order();
 
std::size_t n = m_lock_idxs.size();
 
for (std::size_t i = 0; i < n; ++i)
{
if (! m_mtx_tbl.m_locks[m_lock_idxs[i]].try_lock())
{
// Unlock our previous addresses...
for (std::size_t u = 0; u < i; ++u)
{
m_mtx_tbl.m_locks[m_lock_idxs[i - u - 1]].unlock();
}
 
// backoff algorithm, or whatever...
std::this_thread::yield();
 
// Try again...
i = SIZE_MAX;
 
continue;
}
}
}
_____________________________
 
Remember to include <climits> for SIZE_MAX. The try_lock version does
not even need to be sorted, just unique.
 
 
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Nov 27 12:56AM -0800

On 11/26/2018 11:24 PM, Melzzzzz wrote:
> shared.data_2 = 3
> shared.data_3 = 4
 
> fin!
 
Thanks for trying it out Melzzzzz. :^)
 
The basic algorithm can be useful for many things involving locking.
There is another more "optimistic" version I am tinkering around with
that can be used for n-address based software transactional memory.
 
One note, this is not recursive!
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)