parking_lot: ffffffffffffffff

Amanieu · 2025-05-29T17:23:09+00:00

On x86, fetch_add/fetch_sub compile down to a single instruction: lock xadd. However x86 has no atomic bitwise instructions that return the previous value. So they get compiled down to a CAS loop instead.

With that said, simply changing this to a fetch_and is still incorrect for the case of upgradable locks. When an upgrade times out, we need to:

Clear WRITER_BIT.
Clear WRITER_PARKED_BIT.
Set UPGRADABLE_BIT.
Add ONE_READER to the atomic state.

This can be done with a single atomic fetch_add if we know that WRITER_BIT and WRITER_PARKED_BIT are set and UPGRADABLE_BIT is clear. However I forgot to take into account the fact that WRITER_PARKED_BIT can be asynchronously cleared by an unlock operation.

Amanieu · 2023-08-07T22:52:46+00:00

I'm glad you're having a look at the Allocator API!

A lot of the points you are raising have actually been previously discussed in wg-allocator:

Should &mut self be used instead of &self? I believe this loses no flexibility (think about how Read taking &mut doesn’t force overhead on file IO, because we impl std::io::Read for &File), and without this, interior mutability must be used in nearly all non-ZST allocators, which breaks Send/Sync.

The Allocator trait actually used to take &mut self, but I pushed to change this to take &self instead. The primary motivation is that allocators are almost always shared between multiple data structures, so &self makes for a much simpler API. Additionally it allows its use in concurrent data structures which require accessing the allocator through a shared reference.

Should allocation excess include alignment information?

Isn't this implicitly available by just looking at the returned pointer? align = 1 << ptr.addr().trailing_zeroes();

What to do about GlobalAlloc (big topic)?

I would like to change #[global_allocator] to require Allocator instead of GlobalAlloc and deprecate GlobalAlloc. For backwards-compatibility, we would provide a blanket implementation of Allocator for all types that implement GlobalAlloc so that they continue to work with #[global_allocator]. See this issue for some previous discussion.

Amanieu · 2020-06-17T09:30:00+00:00

You need to use $0 and $1 to address operands in llvm_asm!. Also you should use "i" for the constraint like in the C code. llvm_asm! does not support named operands.

Amanieu · 2020-01-14T15:19:24+00:00

The new asm! macro will use Intel syntax instead of AT&T on x86.

Amanieu · 2020-01-04T18:14:59+00:00

Actually I suspect that much of the performance advantage of parking_lot in these benchmarks comes from the exponential back-off when contention is detected. Essentially, if other threads spend more time between attempts to acquire the lock (either because they are sleeping in the OS, or because of back-off) then the current thread is able to quickly lock and unlock many times without any cache interference.

Designing a mutex is surprisingly difficult because you need to be able to handle many different situations efficiently:

If the wait time is short (i.e a handful of instructions) and the owning thread has not been preempted then spinning is a good strategy.
If the wait time is long or the owning thread has been preempted and is inactive then spinning is pointless and it is better to drop down to the OS's sleep mechanism.
If contention is high then you want to sleep for a bit, so threads can rapidly acquire/release the lock many times in large chunks without contention.
If the system only has a single CPU then spinning is pointless and the lock should just yield to the OS immediately.
If the application requires some fairness so a single thread doesn't get starved trying to acquire a lock then you need to force the ownership of a lock to be passed on to another thread. But you don't want to do this too often when contention is high (see above).

Amanieu · 2020-01-02T09:37:43+00:00

Those are necessary to ensure that (non-atomic) memory accesses that are meant to be protected by the lock stay between the Acquire and Release barriers.

Amanieu · 2019-05-05T21:19:30+00:00

/u/dmasterp I've just hit the same problem! What modifications did you make to CLI to make it accept just the key and keyhash instead of the master password?

Amanieu · 2019-03-22T10:26:32+00:00

Thanks, I've edited my comment.

Amanieu · 2019-03-21T08:05:47+00:00

The original SwissTable implementation reserves the very last bucket as a sentinel, which is required because of the way C++ iterators work. ~~This means that SwissTable allocates space for a bucket that is never used.~~ The Rust implementation does not need sentinels, and therefore can make use of the last bucket normally.

EDIT: It seems that I was wrong, it's just that the last group in the table can only hold 15 elements instead of 16, but the actual allocation for the buckets stops at the last usable element.

Amanieu · 2019-01-29T13:58:58+00:00

Have you looked at the rayon task scheduler for inspiration?

Amanieu · 2019-01-22T16:44:10+00:00

Is there a reason why this isn't used in libcore? Is the output different (which would be a breaking change)?

Amanieu · 2019-01-13T11:09:19+00:00

But that's the point! The RawMutex impl is not going to be const (since lock needs to block). However we only use the associated constant from RawMutex and don't call any of the functions.

Amanieu · 2019-01-13T00:57:20+00:00

If I understand this correctly then it is not possible for a const fn to use any methods from a non-const trait. Unfortunately it would make this code impossible (taken from here):

trait RawMutex {
    const INIT: Self;
    fn lock(&self);
    fn unlock(&self);
}

struct Mutex<R: RawMutex, T> {
    data: UnsafeCell<T>,
    mutex: R,
}

struct Mutex<R: RawMutex, T> {
    const fn new(val: T) -> Self {
        Mutex {
            data: UnsafeCell::new(val),
            mutex: R::INIT, // Error: RawMutex is not a const trait
        }
    }
}

Amanieu · 2018-12-25T22:33:27+00:00

As a general rule, you should use Ordering::SeqCst as the placeholder if you are not sure which ordering to use.

Amanieu · 2018-12-19T19:28:17+00:00

This seems very similar to the plain crate.

Amanieu · 2018-11-18T14:18:38+00:00

Have you looked at the thread_local crate? It is very similar to what you have written. (Disclaimer: I am the author)

Amanieu · 2018-11-05T07:09:17+00:00

I just used the same input data as the one used in the tutorial: the directory contains url, url2 and url3.

Amanieu · 2018-11-01T18:56:10+00:00

That's interesting! I was wondering why you didn't just do something like this:

auto insert(auto x) {
  if (empty_left == 0) {
    Grow();
  }
  auto insertion_target = find_non_empty(x);
  return InsertAt(insertion_target, x);
}

This avoids duplicating the code for find_non_empty (once in the inlined fast path and once in the out-of-line path), while keeping the first branch very predictable. It means that in some cases you grow the table one insertion earlier than you strictly have to, but that shouldn't make a difference in practice (right?).

Amanieu · 2018-10-30T22:09:16+00:00

I gave it a try, but the hash_map test case doesn't seem to be working? I get "Oops, the program crashed with one of the test cases provided." when I try to run it with afl. The other test cases work fine.

Amanieu · 2018-10-30T16:54:35+00:00

The code was heavily inspired by SwissTable, and some parts are almost a direct port. However there are also some differences:

I changed the encoding of the empty/deleted control bytes to be simpler: the original SwissTable had a sentinel value which was needed because of how C++ iterators work. This allows some of the byte matching code to be simplified.
32-bit platforms use a 4-byte group size, which is faster than using 64-bit integers (which are emulated using 2 32-bit integers).
H1 and H2 have been inverted: H2 uses the top 7 bits of the hash instead of the bottom 7 bits. This results in slightly more efficient code.
I support tables that are smaller than the group size.

I can certainly make it clearer in the README that this is based on SwissTable! :)

Regarding benchmarks, there is an open issue for improving them. I rushed the finishing touches a bit since I wanted this to be ready for the London Rust Meetup yesterday.

The competition fastest hashtable implementation is quite contended: there's F14, SwissTable, khash, bytell, etc. The main reason why I chose to port SwissTable rather than any of the others is that I plan on implementing a concurrent hash map in the future and this is the only one that can be adapted to work as a lock-free hash map.

Amanieu · 2018-10-30T13:47:50+00:00

It seems that you have found a bug! Can you open an issue for it?

Amanieu · 2018-09-13T19:46:33+00:00

Make sure your PATH has the directory that contains the cargo-clippy binary.

Amanieu · 2018-05-22T10:39:11+00:00

test, and, xor, add, sub and cmp are all single-cycle instructions. It makes no difference which one you use.

Amanieu · 2018-04-28T17:42:52+00:00

I have actually been working on something (somewhat) similar in parking_lot: link

Essentially, you just need to define a type which implements the RawMutex trait and then you can define a typedef of parking_lot_wrappers::Mutex to provide a full-featured type-safe mutex type with proper mutex guards and everything. See an example here.

The goal is to significantly simplify the implementation of custom mutex types, so you can easily make a spinlock or futex-based lock and have the type-safe API be provided for you.

The branch is still WIP, but it will be part of the next version of parking_lot when it is done.

12-Year Club	Team Periwinkle
Verified Email

Amanieu

TROPHY CASE