AutoHotkey Community

[jetskijoe]

Here is running with 1 thread and just doing 10 stores:

the [store] is in milliseconds is my timing per store

[info]
Starttime=20070610234855
Endtime=20070610235053
totaldays=0.001370
totalhours=0.032882
totalmins=1.972917
totalseconds=118.375000
totalmilliseconds=118375
[store]
10101=4422
10102=4219
10103=3953
10104=3937
10105=3516
10106=18765
10107=18047
10108=17235
10109=16781
10110=17484

[Laszlo]

It means it would finish in 40 minutes (200 stores)? Faster than I expected. Thanks for the detailed info!

[jetskijoe]

Yes I will post the total time tomorrow or later tonight if it finishes before I go to bed.
finished with 200 stores and 100,000 items in each store below is the stats:
[edited]
Starttime=20070610235731
Endtime=20070611004949
totaldays=0.036311
totalhours=0.871467
totalmins=52.288017
totalseconds=3137.281000
totalmilliseconds=3137281

The following is the code I like to add to each of my scripts at the top and bottom to get time times:

[Laszlo]

[Laszlo]

NOTES for the linear congruential generator above:

(1) There is a slight speedup possibility, if we replace "Mod(x,M)" with "x & mask", when M is a power of two, and mask = M – 1. The acceleration is barely measurable (~1%).

(2) We could give an error message, if LcRand is initialized with a too small or too large range.

(3) The main weakness of the linear congruential generator is the regularity of the LS bits. In case of a power of two modulus, the last bit is alternating, the second last bit has a cycle of 4, etc. This regularity is not as strong with general moduli, but for more demanding applications we could improve the complexity of the sequence, which, of course, somewhat slows down the random number generation. One possibility is to use a larger modulus. This results in discarding more generated numbers. The MS bits tell, which value will be discarded, so it is very unpredictable, improving the randomness significantly. The slowdown is moderate: 50..70%.

[Laszlo]

There are three approaches described so far for unique random number generation. The previous post uses a recursive function, which cycles through all possible values. It does not need large memory, very fast, but the randomness is not as good as with the built-in Random command. (The variant, which mixes well the bits of a counter, is an order of magnitude slower.)

The second approach is to generate all the random numbers in advance, and at a request return the next one from the list. It is simple and fast (requiring just one call of a general random number generator for each entry), but uses large memory: several bytes for each value in the range between the smallest and largest requested random numbers, therefore, it is not suitable for very large ranges. 16 million entries (24 bits) represent a practical upper bound with 2GB RAM.

The third approach of unique random number generation uses bookkeeping: keep track of the already generated numbers, and do something at a collision. Bookkeeping can be done with at least three different ways:
-1- Defining dynamic variables (when the internal, highly optimized) variable referencing mechanism of AHK detects collisions). It is the best if the range of the generated random numbers is too large for a bitmap.
-2- Using bitmaps with flags set at the place corresponding to the already generated random numbers
-3- Append to a list the already generated unique random numbers, and search this list for a collision at generating a trial random number. It is the simplest algorithm, but a search in a long list gets slow, making this approach suitable for only a few hundred, maybe a thousand random numbers.

We also have a choice for the action at a collision between unique random numbers generated earlier and a new, trial random number. One possibility is to generate new trial random numbers, until one is found, different from all the ones recorded earlier. A working example (which uses bitmaps as described in -2-) is here. It works pretty fast, until only a few possible numbers remain, when almost all the trial random numbers collide with the recorded ones returned earlier, so the algorithm slows down.

Another strategy at a collision is to check the neighborhood of the colliding number (larger or smaller values), and instead of generating a new trial random number, we return an unused one, close to the value just collided. This can be made much faster by inspecting machine words instead of individual bits, but the randomness is slightly worse. Compiled bitmap functions are available in the Windows NT+ runtime library (ntdll.dll), which further improves the speed:

[Laszlo]

We cannot use the bitmap approach directly if the range of the random numbers is too large (when the -1- algorithm was recommended). For 32-bit random numbers the memory requirement is 2**32 bits = 512 MB. If your PC has 1GB RAM, or less, this would make some applications to be swapped to disk, causing a large, unpredictable delay. We should restrict the memory use less than 128MB.

AHK applications do not normally process more than 67 million numbers (2**26). If we need large random numbers, we can hash them to 28 bits, and use a 28-bit bitmap to detect collisions among the hash values. The bitmap is never more than 25% full, so collisions are rare. Its size, 2**28 bits = 2**25 Bytes = 32MB, is acceptable. There will be a few random numbers rejected, which happen to have the same hash as a different random number, but a repeated random number is always detected. (Note, that this function should not be used when close to all the random numbers in a range are requested: we just waste time with hashing.)

We can employ the RTL bitmap functions, or only AHK commands, using an optimized version of the corresponding function described above:

[Laszlo]

If we want to handle all the different parameter ranges and number of calls efficiently, with good randomness and relatively simple code, we can use the RTL-bitmap functions. At initialization we set up the bitmap, maxing its size to 32MB. We always hash, because testing a condition takes almost the same time as the hash, but the code is simpler this way. Hashing does nothing until the range is at most 2**28.

We use the fix point version of the Random command when the range is less than 32 bits, otherwise its floating point version, which provides 53 random bits at each call. This covers practically all of the use cases, and runs at the possible maximum speed. (If max-min contains more than 53 bits, the least significant bits beyond 53 are rounded, but this is almost never noticeable in the generated random numbers.)

The running time is roughly double of that of the linear congruential generator (4 times slower at huge ranges), but the randomness is better. Compared to the algorithm, which randomly permutes the list of all the possible random numbers and returns the next one from this list, the speed is 65% lower, but the memory consumption is 100 times less.

[rani]

ntdll bitmap usage

hi Lazslo,

1.
what is the syntax to set/get bit 1 or 0 in specific location ?
2.
what is the max number (offset or location) we can set to some Var ,
that represent the bitmap number ?
3.
how can we define tcount of 1's or 0's ?
4.
how can we iterate on all 1's or all 0's one after another

any code syntax will apprciated

[Laszlo]

I don't remember the details. These are the RTL bitmap functions exported:

[rani]

Hi Laszlo

1.
thanks for info
these are the functions I need

pls note I completely, don't know the syntax how to run, by AHK
these functions, even I look on the code demo's in your forum page.
the code syntax and it's params looks strange for me.

can you send some sample code, in AHK, how to run the bitmap functions ?

2. from your answer, the max bitmap var is 32k ?
what is the limit offset I can set/get ? or it is unlimited ?
if I need more range how I can handle it ?

rgrds
Ell

[Laszlo]

[rani]

Hi Laszlo

thank again for info,

1.
if I understand your calculations:
I can set a bit and then get a bit in locations ,let say
in position 128MB (or little less) means:
posBit :=128,000,000
DllCall(SetBis, UInt,&y, UInt,posBit, UInt,1, UChar) ; set bit 1 in position 128mb
and if I set 0 bit to this position I do:
DllCall(ClearBits, UInt,&y, UInt,posBit, UInt,0, UChar) ; set bit 0 in position 128mb

is it correct ?

2. how I iterate on only bits=1 in the var capacity ?,
do I have to Iterate on all the var capacity ?
or there is a function : get next bit 1 from position let say 1001 and so on ...
otherwise to run each time on all var should take long time ?
is there some techinque to run on next bit=1 position ?
is the iterating on bits working fast ?

3. there some functions you define, I don't understand what they mean like:fillmem32,LS64,MS64
all others I understand

I go to test the speed of bit set's/get's


rgrds
Ell

[Laszlo]

- You reference the bitmap with its header, set up in the beginning with RtlInitializeBitMap.
- You can read or write the buffer directly, if you want to
- RtlFindSetBits or RtlFindClearBits will return bit positions, without the need to examine every bit. If you set the HintIndex parameter one larger than what you have processed, the next call will give you the position of the next desired bit, really fast.
- FillMem32 writes the third parameter (UInt32) to the address specified by the 1st parameter. Parameter2 must be 4.
- LS64 returns the position of the least significant bit, which is set (=1) in a 64-bit integer.
- MS64 returns the position of the most significant bit, which is set (=1) in a 64-bit integer.

[rani]

Hi Laszlo,

RtlFindSetBits
in what param I set the RunLen, HintIdx ?
can you send also the syntax of :
RtlFindSetBits
and
RtlFindClearBits
where exactly I put HintIdx (find next from hintIdx) in dllCall ?

I think you are hight level mathematician ?

rgrds
Ell