Oh you've allocated a bit array for every value in the test range, then 
checked for gaps in it?

On Sunday, December 1, 2019 at 2:21:55 PM UTC-8, Michael Jones wrote:
>
> Oh! That's just a bit per integer in the test range 0..total-1. Since Go 
> (and everything else) lacks a bit type, I just type such code 
> automatically. Bytes hold 8 bits. Array size must be rounded up, so
>
> a := make([]byte, (total+8-1)/8)
>
> array index for test integer n is n/8, so "n>>3"
>
> bit index for the j-th bit, counting up from 0 for the 1's place is "1<<j"
>
> j is n%8, so "n&(8-1)"
>
> if mask=1<<(n&(8-1)) then one can test if the bit is set with
>
> a[n>>3] & mask != 0
>
> to set it is 
>
> a[n>>3] |= mask
>
> the values 3 and 8 here are from 8 bits in a byte and 8 = 2**3. if using 
> 64-bit ints they become 6 and 64. 
>
> On Sat, Nov 30, 2019 at 7:06 PM Liam <networ...@gmail.com <javascript:>> 
> wrote:
>
>> I wrote a less-sophisticated version of your test, then realized I'd 
>> misspent my time; all I needed was to change the atomic.Add*() to a 
>> mutex-protected counter, and see whether my app still failed; it did.
>>
>> But since you took the trouble, I read your code, and would like to 
>> understand your collision detector. Could you explain this bit?
>>
>> for _, v := range a {
>>   mask := byte(1 << (v & (8 - 1))) 
>>   index := v >> 3
>>
>>   if tally[index]&mask != 0 { ... }
>>   ...
>> }
>>
>> On Saturday, November 30, 2019 at 5:33:50 PM UTC-8, Michael Jones wrote:
>>>
>>> As a follow-up, some more timing:
>>>
>>> *47088064 atomic increments/sec (my original email above for heavy 
>>> synchronization conflict incrementing)*
>>>
>>> 142049067 atomic increments/sec when each goroutine has its own atomic 
>>> update target. (Not testing global synchronization/mutex, just the 
>>> overhead of congested vs not.)
>>>
>>> 426232527 ordinary "x++" increments in the workers.
>>>
>>> General idea to remember:
>>>
>>> Atomic increment is ~3x slower than simple add when uncontested.
>>> Highly contested atomic increment is ~3x closer than uncontested, 
>>> therefore ~9x-10x slower than simple add.
>>>
>>> 10x is not insignificant, but is nevertheless remarkable for a reliable 
>>> atomic operation. This was once, "back in the day", a remarkably expensive 
>>> operation, an a feat of genius to accomplish (Dekker's Algorithm 
>>> <https://en.wikipedia.org/wiki/Dekker%27s_algorithm>). That it is now 
>>> just a number-of-fingers cycles is fantastic progress!
>>>
>>> On Sat, Nov 30, 2019 at 3:38 PM Michael Jones <michae...@gmail.com> 
>>> wrote:
>>>
>>>> Liam,
>>>>
>>>> I just wrote a little stress test program for you. Maybe it will make 
>>>> you less stressed. ;-)
>>>> https://play.golang.org/p/5_7Geyczd1V
>>>>
>>>> 4 CPU 2016 MacBook Pro:
>>>>
>>>> *celeste:atom mtj$ go run main.go*
>>>> *32 concurrent workers*
>>>> *128 batches of 1048576 atomic increments, 134217728 total increments*
>>>> *2.850 seconds elapsed, 47088064 atomic increments/sec*
>>>> *0 collisions*
>>>>
>>>>
>>>> 18 CPU 2019 iMacPro:
>>>>
>>>> *plum:atom mtj$ go run main.go*
>>>> *32 concurrent workers*
>>>> *128 batches of 1048576 atomic increments, 134217728 total increments*
>>>> *2.730 seconds elapsed, 49167382 atomic increments/sec*
>>>> *0 collisions*
>>>>
>>>>
>>>> Exhaustive demonstration is no proof, but changing the parameters here 
>>>> may increase your comfort.
>>>>
>>>> Michael
>>>>
>>>> On Sat, Nov 30, 2019 at 1:02 PM Robert Engels <ren...@ix.netcom.com> 
>>>> wrote:
>>>>
>>>>> If this was broken I think a lot of things would break. 
>>>>>
>>>>> On Nov 30, 2019, at 1:56 PM, Liam <networ...@gmail.com> wrote:
>>>>>
>>>>> 
>>>>> The stress test for my app fails frequently with what looks like a 
>>>>> collision in atomic.AddUint64() results, so I wondered whether I had 
>>>>> misunderstood atomic-add.
>>>>>
>>>>> So far I can't reproduce it with a small program, so I've probably 
>>>>> misunderstood my app :-)
>>>>>
>>>>> On Friday, November 29, 2019 at 6:41:39 PM UTC-8, Kurtis Rader wrote:
>>>>>>
>>>>>> On Fri, Nov 29, 2019 at 6:21 PM Liam <networ...@gmail.com> wrote:
>>>>>>
>>>>>>> Does atomic.AddInt32(&x, 1) always yield unique values for 
>>>>>>> concurrent callers?
>>>>>>>
>>>>>>> I'm guessing not, because (I think) I'm seeing that two callers get 
>>>>>>> x+2, neither gets x+1.
>>>>>>>
>>>>>>
>>>>>> That shouldn't happen, AFAICT. Can you share the code where the 
>>>>>> incorrect behavior is occurring? Or, preferably, a simple reproducer 
>>>>>> program?
>>>>>>   
>>>>>>
>>>>>>> Is there a way to generate unique values with pkg atomic, or is a 
>>>>>>> mutex required?
>>>>>>>
>>>>>>
>>>>>> Keep in mind that atomic.AddInt32() has the usual two's-complement  
>>>>>> overflow semantics. If all you want is a generation counter you really 
>>>>>> should be using a uint32 and atomic.AddUint32(). Also, depending on your 
>>>>>> preferences and performance considerations you might find it preferable 
>>>>>> to 
>>>>>> use a channel that holds a single int, or small number of ints, that is 
>>>>>> fed 
>>>>>> by a producer goroutine and consumed by any context needing a uniq ID. 
>>>>>> That 
>>>>>> makes it easier to abstract the generation of "unique" ints so that they 
>>>>>> satisfy other constraints (e.g., they must be even, odd, prime, etc.).
>>>>>>
>>>>>> -- 
>>>>>> Kurtis Rader
>>>>>> Caretaker of the exceptional canines Junior and Hank
>>>>>>
>>>>> -- 
>>>>> You received this message because you are subscribed to the Google 
>>>>> Groups "golang-nuts" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send 
>>>>> an email to golan...@googlegroups.com.
>>>>> To view this discussion on the web visit 
>>>>> https://groups.google.com/d/msgid/golang-nuts/4f62dfff-6895-4aaa-9f0d-b635d5ba7ea7%40googlegroups.com
>>>>>  
>>>>> <https://groups.google.com/d/msgid/golang-nuts/4f62dfff-6895-4aaa-9f0d-b635d5ba7ea7%40googlegroups.com?utm_medium=email&utm_source=footer>
>>>>> .
>>>>>
>>>>> -- 
>>>>> You received this message because you are subscribed to the Google 
>>>>> Groups "golang-nuts" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send 
>>>>> an email to golan...@googlegroups.com.
>>>>> To view this discussion on the web visit 
>>>>> https://groups.google.com/d/msgid/golang-nuts/C7B99DEA-D183-44EF-9EDA-0B1841AB9DE5%40ix.netcom.com
>>>>>  
>>>>> <https://groups.google.com/d/msgid/golang-nuts/C7B99DEA-D183-44EF-9EDA-0B1841AB9DE5%40ix.netcom.com?utm_medium=email&utm_source=footer>
>>>>> .
>>>>>
>>>>
>>>>
>>>> -- 
>>>>
>>>> *Michael T. jonesmichae...@gmail.com*
>>>>
>>>
>>>
>>> -- 
>>>
>>> *Michael T. jonesmichae...@gmail.com*
>>>
>> -- 
>> You received this message because you are subscribed to the Google Groups 
>> "golang-nuts" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to golan...@googlegroups.com <javascript:>.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/golang-nuts/4d091a92-707a-40dc-8d1b-f12e10426438%40googlegroups.com
>>  
>> <https://groups.google.com/d/msgid/golang-nuts/4d091a92-707a-40dc-8d1b-f12e10426438%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>
>
> -- 
>
> *Michael T. jonesmichae...@gmail.com <javascript:>*
>

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/4a457f1f-7956-474a-b29a-909aee0e55c3%40googlegroups.com.

Reply via email to