Sorry, I hadn’t looked at the code, but after reviewing doesn’t your code not
detect the case where a value was skipped ? (... not that it could happen - but
for completeness of the robust test)
> On Dec 1, 2019, at 10: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). 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.
>>>>>>>>
>>>>>>>> --
>>>>>>>> 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.
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> Michael T. Jones
>>>>>>> michae...@gmail.com
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Michael T. Jones
>>>>>> michae...@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.
>>>>
>>>>
>>>> --
>>>> Michael T. Jones
>>>> michae...@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.
>>
>> --
>> 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.
>
>
> --
> Michael T. Jones
> 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/CALoEmQzoqrEgfPQ_%3DyeRBN2FPby7kHqrmN-qqFH6RrqBMH6r9A%40mail.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/A5B5DC63-90F2-4AD9-B5CE-1A8993FFC1D7%40ix.netcom.com.
