I tried to use futexes for my pow10-function.
Is the usage correct ?
Maybe, but it's not needed and makes the code more complex,
redundant and potentially a bit slower.
11.04.2024 12:05 Bonita Montero kirjutas:
I tried to use futexes for my pow10-function.
Is the usage correct ?
Maybe, but it's not needed and makes the code more complex, redundant
and potentially a bit slower.
C++ statics' initialization is guaranteed to be thread-safe since C++11. Just put your initialization logic into a separate function and use this
for initializing your static variable. C++ will perform any needed multi-thread locking automatically, adding ones own explicit locks will
not make it faster.
I tried to use futexes for my pow10-function.
Is the usage correct ?
#include <bit>
#include <atomic>
#include <array>
#include <mutex>
#include "xmath.h"
using namespace std;
double pow10( int64_t exp )
{
constexpr uint64_t EXP_MASK = 0x7FFull << 52;
// table for binary exponentation with 10 ^ (2 ^ N)
static array<double, 64> tenPows;
// table initialized ?
if( static atomic_bool once( false ); !once.load( memory_order_acquire ) )
{
once.wait( false, memory_order_acquire );
if( !once.load( memory_order_relaxed ) )
{
// no: calculate table
for( double p10x2xN = 10.0; double &pow : tenPows )
pow = p10x2xN,
p10x2xN *= p10x2xN;
// set initialized flag with release semantics
once.store( true, memory_order_release );
once.notify_all();
}
}
// begin with 1.0 since x ^ 0 = 1
double result = 1.0;
// unsigned exponent
uint64_t uExp = exp >= 0 ? exp : -exp;
// highest set bit of exponent
size_t bit = 63 - countl_zero( uExp );
// bit mask to highest set bit
uint64_t mask = 1ull << bit;
// loop as long as there are bits in unsigned exponent
for( ; uExp; uExp &= ~mask, mask >>= 1, --bit )
// bit set ?
if( uExp & mask )
{
// yes: multiply result by 10 ^ (bit + 1)
result *= tenPows[bit];
// overlow ?
if( (bit_cast<uint64_t>( result ) & EXP_MASK) == EXP_MASK )
// yes: result wouldn't change furhter; stop
break;
}
// return 1 / result if exponent is negative
return exp >= 0 ? result : 1.0 / result;
};
On 4/11/2024 2:05 AM, Bonita Montero wrote:[...]
I tried to use futexes for my pow10-function.
Is the usage correct ?
#include <bit>
#include <atomic>
#include <array>
#include <mutex>
#include "xmath.h"
using namespace std;
double pow10( int64_t exp )
{
constexpr uint64_t EXP_MASK = 0x7FFull << 52;
// table for binary exponentation with 10 ^ (2 ^ N)
static array<double, 64> tenPows;
// table initialized ?
if( static atomic_bool once( false ); !once.load(
memory_order_acquire ) )
{
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate when
a futex wait returns. Kind of akin to a condvar.
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate when
a futex wait returns. ....
if( !once.load( memory_order_relaxed ) )
Am 20.04.2024 um 06:26 schrieb Chris M. Thomasson:
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate
when a futex wait returns. ....
if( !once.load( memory_order_relaxed ) )
What's that ?
On 4/19/2024 10:17 PM, Bonita Montero wrote:
Am 20.04.2024 um 06:26 schrieb Chris M. Thomasson:
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate
when a futex wait returns. ....
if( !once.load( memory_order_relaxed ) )
What's that ?
Humm... Think if three threads hit once.wait, and the all get woken up spuriously, once is still false. Now all three threads do your
if( !once.load( memory_order_relaxed ) )
once is false, and all three threads go into your init code at the same time. What am I missing here?
if( static atomic_bool once( false ); !once.load( memory_order_acquire
) )
{
// three threads A, B and C wait.
once.wait( false, memory_order_acquire );
// A, B, get here on a spurious wake.
// oh shit!
if( !once.load( memory_order_relaxed ) )
{
// all three threads are going to see once as being false
// they are all in the init code!
// you are now fucked!
What am I missing?
On 4/20/2024 2:47 AM, Chris M. Thomasson wrote:
On 4/19/2024 10:17 PM, Bonita Montero wrote:
Am 20.04.2024 um 06:26 schrieb Chris M. Thomasson:
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate
when a futex wait returns. ....
if( !once.load( memory_order_relaxed ) )
What's that ?
Humm... Think if three threads hit once.wait, and the all get woken up
spuriously, once is still false. Now all three threads do your
if( !once.load( memory_order_relaxed ) )
once is false, and all three threads go into your init code at the
same time. What am I missing here?
if( static atomic_bool once( false ); !once.load(
memory_order_acquire ) )
{
// three threads A, B and C wait.
once.wait( false, memory_order_acquire );
// A, B, get here on a spurious wake.
// oh shit!
if( !once.load( memory_order_relaxed ) )
{
// all three threads are going to see once as being false
// they are all in the init code!
// you are now fucked!
What am I missing?
You probably want something like this pseudo-code, untested typed in the newsreader:
________________________
atomic<int> g_state = 0;
if (! g_state.exchange(1, relaxed))
{
// critical section
// do your thing...
g_state.store(2, release);
g_state.notify_all(relaxed);
}
else
{
while (g_state.load(acquire) != 2)
{
g_state.wait(1, relaxed);
}
}
________________________
?
I tried to use futexes for my pow10-function.[...]
Is the usage correct ?
Am 20.04.2024 um 06:26 schrieb Chris M. Thomasson:
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate
when a futex wait returns. ....
if( !once.load( memory_order_relaxed ) )
What's that ?
On 4/19/2024 10:17 PM, Bonita Montero wrote:
Am 20.04.2024 um 06:26 schrieb Chris M. Thomasson:
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate
when a futex wait returns. ....
if( !once.load( memory_order_relaxed ) )
What's that ?
Still not 100% sure if atomic::wait is allowed to return spuriously. The docs seem to say that it cannot? That means that it must do a double
check in a loop in its logic. This is a lot different than normal futex behavior.
https://en.cppreference.com/w/cpp/atomic/atomic/wait
I tried to use futexes for my pow10-function.
Is the usage correct ?
#include <bit>
#include <atomic>
#include <array>
#include <mutex>
#include "xmath.h"
using namespace std;
double pow10( int64_t exp )
{
constexpr uint64_t EXP_MASK = 0x7FFull << 52;
// table for binary exponentation with 10 ^ (2 ^ N)
static array<double, 64> tenPows;
// table initialized ?
if( static atomic_bool once( false ); !once.load( memory_order_acquire ) )
{
once.wait( false, memory_order_acquire );
if( !once.load( memory_order_relaxed ) )
{
// no: calculate table
for( double p10x2xN = 10.0; double &pow : tenPows )
pow = p10x2xN,
p10x2xN *= p10x2xN;
// set initialized flag with release semantics
once.store( true, memory_order_release );
once.notify_all();
}
}
// begin with 1.0 since x ^ 0 = 1
double result = 1.0;
// unsigned exponent
uint64_t uExp = exp >= 0 ? exp : -exp;
// highest set bit of exponent
size_t bit = 63 - countl_zero( uExp );
// bit mask to highest set bit
uint64_t mask = 1ull << bit;
// loop as long as there are bits in unsigned exponent
for( ; uExp; uExp &= ~mask, mask >>= 1, --bit )
// bit set ?
if( uExp & mask )
{
// yes: multiply result by 10 ^ (bit + 1)
result *= tenPows[bit];
// overlow ?
if( (bit_cast<uint64_t>( result ) & EXP_MASK) == EXP_MASK )
// yes: result wouldn't change furhter; stop
break;
}
// return 1 / result if exponent is negative
return exp >= 0 ? result : 1.0 / result;
};
On 4/11/2024 2:05 AM, Bonita Montero wrote:
I tried to use futexes for my pow10-function.[...]
Is the usage correct ?
I coded up a quick and dirty little test for a futex based double
checked lock.
Can you run it?
______________________________
#include <iostream>
#include <functional>
#include <atomic>
#include <thread>
#include <chrono>
#include <cstdlib>
// Ughh, some quick test params...
#define CT_L2_CACHE 128UL
#define CT_THREAD_N 8UL
#define CT_ITER_N 10000000UL
struct alignas(CT_L2_CACHE) ct_double_checked_lock
{
std::atomic<unsigned int> m_state = 0;
int m_var = 0;
void init()
{
unsigned int state = 0;
if (m_state.compare_exchange_strong(
state,
1,
std::memory_order_acquire))
{
// critical section
std::this_thread::yield();
m_var += 123;
std::this_thread::yield();
m_state.store(2, std::memory_order_release);
m_state.notify_all();
}
else^^^^^^^^^^^^^^^^^^^^
{
while (m_state.load(std::memory_order_acquire) != 2)
{
m_state.wait(1, std::memory_order_relaxed);
}
}
}
};
Oh, wow. So, this would mean I can get around that while loop in a slow^^^^^^^^^^^^^^
path of my DCL code. This is going against my previous knowledge of
futexes. C++ might as well have a std::wait_strong/weak akin to compare_exchange_strong/weak... Anyway, so I should be able to get rid
of that loop:
_____________
while (m_state.load(std::memory_order_acquire) != 2)
{
m_state.wait(1, std::memory_order_relaxed);
}
_____________
Into just:
_____________
if (m_state.load(std::memory_order_acquire) != 2)
{
// slow path
m_state.wait(1, std::memory_order_relaxed);
// no need to recheck because m_state == 2 here for sure.
}
_____________
Humm... This goes against my futex ways! If C++ really does do its own internal check and automatically handles any spurious wakes from the underlying impl, then, well. Okay. Just not what I expected.
}[...]
}
};
Humm... This goes against my futex ways! If C++ really does do its own
internal check and automatically handles any spurious wakes from the
underlying impl, then, well. Okay. Just not what I expected.
On 4/20/2024 3:55 PM, Chris M. Thomasson wrote:
On 4/19/2024 10:17 PM, Bonita Montero wrote:
Am 20.04.2024 um 06:26 schrieb Chris M. Thomasson:
once.wait( false, memory_order_acquire );
Any problems with spurious wakes? You need to recheck the predicate
when a futex wait returns. ....
if( !once.load( memory_order_relaxed ) )
What's that ?
Still not 100% sure if atomic::wait is allowed to return spuriously.
The docs seem to say that it cannot? That means that it must do a
double check in a loop in its logic. This is a lot different than
normal futex behavior.
https://en.cppreference.com/w/cpp/atomic/atomic/wait
Still, your logic is still going to have problems.
I tried to use futexes for my pow10-function.[...]
Is the usage correct ?
Sysop: | DaiTengu |
---|---|
Location: | Appleton, WI |
Users: | 915 |
Nodes: | 10 (1 / 9) |
Uptime: | 25:37:18 |
Calls: | 12,169 |
Calls today: | 1 |
Files: | 186,521 |
Messages: | 2,234,047 |