- Lock-free LRU-cache-algorithm - 9 Updates
- newbie question: exceptions - 9 Updates
- newbie question: exceptions - 1 Update
- Performance of unaligned memory-accesses - 6 Updates
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Aug 12 04:26PM -0700 On 8/8/2019 11:59 PM, Bonita Montero wrote: > look like? LRU-caches are only possible with doubly-linked lists. > So I thought this woudn't be possible lock-free. But maybe I'm > wrong here and someone can give me an idea. There are lock-free doubly-linked lists. However, the following algorihtm might of of interest to you: https://groups.google.com/d/topic/comp.lang.c++/sV4WC_cBb9Q/discussion It is a simple deadlock free hashed mutex algorihtm. |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 10:24AM +0200 > algorihtm might of of interest to you: > https://groups.google.com/d/topic/comp.lang.c++/sV4WC_cBb9Q/discussion > It is a simple deadlock free hashed mutex algorihtm. Your code might help exchaning two elements in a lock-free list with a low likehood of a collision. But the thing I need is a LRU-list which scales similar. The difference here is that an element is always pushed to the top when it is touched. So every thread contending on that must also lock the head-pointers. So if there is always a common´structure locked, I can stick with a single lock and I would get the same effi- ciency as your code. |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 10:42AM +0200 > It is a simple deadlock free hashed mutex algorihtm. BTW: Your hashing could be cleverer. With ... return (std::size_t)(((ptr_uint << 9) * 103) % m_locks.size()); ... you multiply ptr_uint by 52.736. That's not a good hash-function. Better mutitply by the largest prime fitting in a size_t. You can get them here: https://primes.utm.edu/lists/2small/ So the maximum prime for 32 bit size_t would be 0xFFFFFFFB, the maximum prime for 64 bit would be 18.446.744.073.709.551.557 (my calculator can't convert that to hex). |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 11:19AM +0200 Am 13.08.2019 um 10:42 schrieb Bonita Montero: > So the maximum prime for 32 bit size_t would be 0xFFFFFFFB, the > maximum prime for 64 bit would be 18.446.744.073.709.551.557 (my > calculator can't convert that to hex). So finally it is 0xffffffffffffffc5. |
| Josef Moellers <josef.moellers@invalid.invalid>: Aug 13 11:42AM +0200 On 13.08.19 11:19, Bonita Montero wrote: >> maximum prime for 64 bit would be 18.446.744.073.709.551.557 (my >> calculator can't convert that to hex). > So finally it is 0xffffffffffffffc5. echo "obase=16; 18446744073709551557" | bc Josef |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 12:47PM +0200 > Better mutitply by the largest prime fitting in a size_t. ... I forgot that this is a rule only if this prime isn't a meresenne-prime. If it is, take the next lower one. |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Aug 13 03:03PM -0700 On 8/13/2019 1:42 AM, Bonita Montero wrote: >> It is a simple deadlock free hashed mutex algorihtm. > BTW: Your hashing could be cleverer. Big Time! yikes. > So the maximum prime for 32 bit size_t would be 0xFFFFFFFB, the > maximum prime for 64 bit would be 18.446.744.073.709.551.557 (my > calculator can't convert that to hex). Yes. indeed. When I was coding my algorihtm, well, just used a stupid simple hash of a pointer address. The posted version is in an embryonic, example state. Actually, the algorihtm can be used as a lock-based STM. It can use try_locks to detect conflict and try to do something else before it actually blocks on a mutex within the main table. So, it can be combined with a lock-free TM. Use the locks as needed. Wrt the slowpath, or for fallback conditions. Funny thing, since it is based on hashing pointer addresses, well, each run of the same program can use different locks each time. If the OS randomizes where the program can get its memory from. Pointer A, run 1 is different in "value" of Pointer A, run 2. ;^) |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Aug 13 03:17PM -0700 On 8/13/2019 3:03 PM, Chris M. Thomasson wrote: > Yes. indeed. When I was coding my algorihtm, well, just used a stupid > simple hash of a pointer address. The posted version is in an embryonic, > example state. The hash needs to try and avoid collisions. Each collision, wrt different pointers mapping into the same mutex, well, that is BAD. |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Aug 13 03:31PM -0700 On 8/13/2019 3:03 PM, Chris M. Thomasson wrote: >>> It is a simple deadlock free hashed mutex algorihtm. >> BTW: Your hashing could be cleverer. > Big Time! yikes. [...] > run of the same program can use different locks each time. If the OS > randomizes where the program can get its memory from. Pointer A, run 1 > is different in "value" of Pointer A, run 2. Sorry for the message flood, but, failed try_locks can be used to build meta data about how the table of mutexes is being used over time. |
| Jivanmukta <jivanmukta@poczta.onet.pl>: Aug 13 04:34PM +0200 I am learning C++ and I have a question: why: throw exception(); and not: throw new exception(); |
| Jivanmukta <jivanmukta@poczta.onet.pl>: Aug 13 04:38PM +0200 W dniu 13.08.2019 o 16:34, Jivanmukta pisze: > throw exception(); > and not: > throw new exception(); Does it make sense to code: MyClass *myObj = MyClass(); instead of: MyClass *myObj = new MyClass(); |
| Szyk Cech <szykcech@spoko.pl>: Aug 13 05:01PM +0200 NTG: alt.comp.lang.learn.c-c++ |
| Bo Persson <bo@bo-persson.se>: Aug 13 05:02PM +0200 On 2019-08-13 at 16:38, Jivanmukta wrote: >> throw exception(); >> and not: >> throw new exception(); You can do either - throw an exception object or throw a pointer. In the latter case you have to catch a pointer and also remember to delete it somewhere. Extra work. And an extra allocation. So most people prefer the first version. > MyClass *myObj = MyClass(); > instead of: > MyClass *myObj = new MyClass(); No. You can just do MyClass myObj; and be done with it. No need for pointers here. Bo Persson |
| "Öö Tiib" <ootiib@hot.ee>: Aug 13 08:03AM -0700 On Tuesday, 13 August 2019 17:38:34 UTC+3, Jivanmukta wrote: > > throw exception(); > > and not: > > throw new exception(); First throws exception, second throws pointer to exception. Second does allocate memory dynamically and you need to delete the caught pointer to exception somewhere after throwing for not to leak it but the object's lifetime is not bound to catch site. So with second there are more work both for you and for the resulting program but also more flexibility. Otherwise there are no why and why not level of difference. > Does it make sense to code: > MyClass *myObj = MyClass(); No. It is usually syntax error, and when not takes unusual design of MyClass. Typical is: MyClass myObj{}; > instead of: > MyClass *myObj = new MyClass(); There is similar extra work, like it was with exceptions. It is up to you, programmer to decide if that is needed by your program design or not. I can't tell it from abstract one-liners. |
| Szyk Cech <szykcech@spoko.pl>: Aug 13 05:03PM +0200 On 13.08.2019 16:34, Jivanmukta wrote: > throw exception(); > and not: > throw new exception(); Ju throw objekt of any walue - not limited tu pointers... |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 05:03PM +0200 > throw exception(); > and not: > throw new exception(); Because new might throw an exception itself (bad_alloc) and you would throw a pointer and not an object itself. Where the memory for the exception-object is allocated is unspecified. Can anyone tell what the usual implementations are? |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 05:39PM +0200 > Beginners should never use "new" in modern C++. If the use shared_ptr<T> or unique_ptr<T> with the constructor -parameters for the new'd object and get a complex compiler-error because of the parmeters don't fit in the headers of the smart- pointer-classes they'd better should use raw pointers and new and ignore that their code is not memory-collapse-safe for the first time. |
| red floyd <dont.bother@its.invalid>: Aug 13 09:33AM -0700 On 8/13/2019 7:34 AM, Jivanmukta wrote: > throw exception(); > and not: > throw new exception(); Aside from what everyone else has said... Because C++ isn't Java. |
| ram@zedat.fu-berlin.de (Stefan Ram): Aug 13 03:31PM >>throw exception(); >>and not: >>throw new exception(); Beginners should never use "new" in modern C++. When you have seen "new", it could have been in an outdated C++ book or in a Java book. Check out: "Programming: Principles and Practice Using C++ ", by Bjarne Stroustrup, 2014 (no earlier!). Section 5.6, Exceptions. |
| James Kuyper <jameskuyper@alumni.caltech.edu>: Aug 12 04:38PM -0700 On Monday, August 12, 2019 at 12:24:24 PM UTC-4, Bonita Montero wrote: > >> No, the structure-size is rounded up for that. > > Not when #pragma pack(1) is used like they discussed. ... > There wasn't any #pragma pack in the former example. Please don't interrupt a conversation if you're not willing to pay sufficient attention to avoid making remarks that betray your lack of attention. Keith's message dated Sun, 11 Aug 2019 17:07:21 -0700 included a #pragma pack(1) directive, and all of the subsequent discussion has been about the significance of such a directive. Bart snipped that line in his response, but his message and Keith's response both refer to pack(1) as a shorthand for #pragma pack(1). If you didn't know what "pack(1)" was referring to, you should have asked. |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 02:28AM +0200 >> No, everyone can guess from the "0x3" that pI points to a 32 bit >> integer - exept you. > No it can't. pI can point to anything. 0x3 wouldn't make sense for a unaligned-check pointer to a char. |
| Melzzzzz <Melzzzzz@zzzzz.com>: Aug 13 01:08AM >>> integer - exept you. >> No it can't. pI can point to anything. > 0x3 wouldn't make sense for a unaligned-check pointer to a char. Again, I commented assertion that unaligned access causes undefined behavior. And I don't care what 0x3 means. -- press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| Ralf Goertz <me@myprovider.invalid>: Aug 13 08:53AM +0200 Am Sun, 11 Aug 2019 18:40:55 +0200 > p = &i; > fInc( p ); > } After changing S to struct S { char c; int i; } __attribute__((packed)); I get gcc -c packed.cc -o packed packed.cc: In function 'void f()': packed.cc:17:10: warning: taking address of packed member of 'S' may result in an unaligned pointer value [-Waddress-of-packed-member] 17 | p = &s.i; | ^~~~ |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 09:18AM +0200 > packed.cc:17:10: warning: taking address of packed member of 'S' may > result in an unaligned pointer value [-Waddress-of-packed-member] 17 | > p = &s.i; | ^~~~ Ok, I have an older gcc-version on my WSL. But that's just a warning and I think it's there because for comatibility- and performance-reasons. But as I said a compiler will generate correct code. If it runs at last simply depends on the CPU / operating-system. |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 13 04:03PM +0200 > Again, I commented assertion that unaligned access causes undefined > behavior. And I don't care what 0x3 means. As I said that's not undefined behaviour because the compiler would be unable to generate the code as expected but because the CPU might fail / trap an unaligned access at runtime and the OS might emulate tzhe unaligned access or not. So it depends on the platform you target. |
| 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. |
No comments:
Post a Comment