"Oh you've allocated a bit array for every value in the test range, then
checked for gaps in it?"
Yes. What I should have said. (Though the test looks not for gaps but for
two pigeons in one hole, but the same idea.)
On Sun, Dec 1, 2019 at 8:44 PM Michael Jones <michael.jo...@gmail.com>
wrote:
> not necessary as the testing and updating is only done in one place by one
> the main goroutine.
>
> On Sun, Dec 1, 2019 at 7:46 PM Robert Engels <reng...@ix.netcom.com>
> wrote:
>
>> The updating of the bit array if shared needs to atomic as well, probably
>> with a read and cas.
>>
>> On Dec 1, 2019, at 9:19 PM, Liam <networkimp...@gmail.com> wrote:
>>
>>
>> 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> 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.
>>>> 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*
>>>
>> --
>> 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
>> <https://groups.google.com/d/msgid/golang-nuts/4a457f1f-7956-474a-b29a-909aee0e55c3%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 golang-nuts+unsubscr...@googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/golang-nuts/4C46C912-25BB-459C-96DE-7D643F132757%40ix.netcom.com
>> <https://groups.google.com/d/msgid/golang-nuts/4C46C912-25BB-459C-96DE-7D643F132757%40ix.netcom.com?utm_medium=email&utm_source=footer>
>> .
>>
>
>
> --
>
> *Michael T. jonesmichael.jo...@gmail.com <michael.jo...@gmail.com>*
>
--
*Michael T. jonesmichael.jo...@gmail.com <michael.jo...@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 golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/CALoEmQx_3A7Dc_SkimV8s_NpAy7bw27bfd_gmKt2CvfFZ-znXg%40mail.gmail.com.
