26-Jul-2013 14:47, Dmitry Olshansky пишет:
> 26-Jul-2013 01:25, Walter Bright пишет:

>> The slowness was in the frackin' "convert the hash to an index in the
>> bucket", which is a modulus operation.
>
> Then it's past due to finally stop the madness of modulo prime table and
> use a power of 2 size. In essence what modulo prime does is simply
> enhancing the quality of your hash function w.r.t. collisions (it helps
> to distribute values more evenly).
>
> Any of new decent hashes are good enough to work with plain slice the
> lower bits approach.
>

To be more concrete:
Spooky hash
http://burtleburtle.net/bob/hash/spooky.html (Public domain)
S-box hash
http://home.comcast.net/~bretm/hash/10.html (Published paper)

Or even a good ol' FNV (Public domain)
http://isthe.com/chongo/tech/comp/fnv/#FNV-1a

-- 
Dmitry Olshansky

On 7/26/2013 5:11 AM, Dmitry Olshansky wrote:
> 26-Jul-2013 14:47, Dmitry Olshansky пишет:
>> 26-Jul-2013 01:25, Walter Bright пишет:
>
>>> The slowness was in the frackin' "convert the hash to an index in the
>>> bucket", which is a modulus operation.
>>
>> Then it's past due to finally stop the madness of modulo prime table and
>> use a power of 2 size. In essence what modulo prime does is simply
>> enhancing the quality of your hash function w.r.t. collisions (it helps
>> to distribute values more evenly).
>>
>> Any of new decent hashes are good enough to work with plain slice the
>> lower bits approach.
>>
>
> To be more concrete:
> Spooky hash
> http://burtleburtle.net/bob/hash/spooky.html (Public domain)
> S-box hash
> http://home.comcast.net/~bretm/hash/10.html (Published paper)
>
> Or even a good ol' FNV (Public domain)
> http://isthe.com/chongo/tech/comp/fnv/#FNV-1a
>

How about a pull request so we can try it out?

26-Jul-2013 23:17, Walter Bright пишет:
> On 7/26/2013 5:11 AM, Dmitry Olshansky wrote:
>> 26-Jul-2013 14:47, Dmitry Olshansky пишет:
>>> 26-Jul-2013 01:25, Walter Bright пишет:
>>
>>>> The slowness was in the frackin' "convert the hash to an index in the
>>>> bucket", which is a modulus operation.
>>>
>>> Then it's past due to finally stop the madness of modulo prime table and
>>> use a power of 2 size. In essence what modulo prime does is simply
>>> enhancing the quality of your hash function w.r.t. collisions (it helps
>>> to distribute values more evenly).
>>>
>>> Any of new decent hashes are good enough to work with plain slice the
>>> lower bits approach.
>>>
>>
>> To be more concrete:
>> Spooky hash
>> http://burtleburtle.net/bob/hash/spooky.html (Public domain)
>> S-box hash
>> http://home.comcast.net/~bretm/hash/10.html (Published paper)
>>
>> Or even a good ol' FNV (Public domain)
>> http://isthe.com/chongo/tech/comp/fnv/#FNV-1a
>>
>
> How about a pull request so we can try it out?

Thought as much.
I'll be away at the weekends but I'll surely try my hand at it afterwards.

-- 
Dmitry Olshansky

On Friday, 26 July 2013 at 00:08:21 UTC, Leandro Lucarella wrote:
> Walter Bright, el 25 de July a las 14:27 me escribiste:
>> On 7/25/2013 11:49 AM, Dmitry S wrote:
>> >I am also confused by the numbers. What I see at the end of the article is
>> >"21.56 seconds, and the latest development version does it in 12.19", which is
>> >really a 43% improvement. (Which is really great too.)
>> 
>> 21.56/12.19 is 1.77, i.e. a >75% improvement in speed.
>
> This is certainly misleading, is very easy to be confused with a time
> reduction of 75%, which one would expect to be 1/4 of the original time.
> :)

No, a division by 4 of the total time would be a 300% improvement in speed. The article's title looks correct to me.

SomeDude, el 27 de July a las 20:27 me escribiste:
> On Friday, 26 July 2013 at 00:08:21 UTC, Leandro Lucarella wrote:
> >Walter Bright, el 25 de July a las 14:27 me escribiste:
> >>On 7/25/2013 11:49 AM, Dmitry S wrote:
> >>>I am also confused by the numbers. What I see at the end of
> >>>the article is
> >>>"21.56 seconds, and the latest development version does it in
> >>>12.19", which is
> >>>really a 43% improvement. (Which is really great too.)
> >>
> >>21.56/12.19 is 1.77, i.e. a >75% improvement in speed.
> >
> >This is certainly misleading, is very easy to be confused with a
> >time
> >reduction of 75%, which one would expect to be 1/4 of the original
> >time.
> >:)
> 
> No, a division by 4 of the total time would be a 300% improvement in speed. The article's title looks correct to me.

Again, I never said is incorrect, I said is easily to read it incorrectly, which ends up sending a wrong message.

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
Wake from your sleep,
the drying of your tears,
Today we escape, we escape.

Walter Bright, el 25 de July a las 18:33 me escribiste:
> On 7/25/2013 4:15 PM, Leandro Lucarella wrote:
> >Walter Bright, el 25 de July a las 14:27 me escribiste:
> >>On 7/25/2013 11:49 AM, Dmitry S wrote:
> >>>I am also confused by the numbers. What I see at the end of the article is "21.56 seconds, and the latest development version does it in 12.19", which is really a 43% improvement. (Which is really great too.)
> >>
> >>21.56/12.19 is 1.77, i.e. a >75% improvement in speed.
> >
> >This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :)
> 
> I don't think it's misleading at all. Speed is distance/time. A change in speed (which is the title) is the reciprocal of a change in time.
> 
> For example, a doubling of speed (100% increase) is a halving of
> time (50% reduction).

I know is technically right, I'm just saying it can be easily confused for something else that looks much better than the actual (very good) reality, and in this case is misleading.

If you say something that's technically correct but hard to understand, you are not communicating your message effectively.

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
No existiría el sonido del mar si faltara en la vida oreja y caracol.
	-- Ricardo Vaporeso. Cosquín, 1908.

On 26.07.2013 01:15, Leandro Lucarella wrote:
> Walter Bright, el 25 de July a las 14:27 me escribiste:
>> On 7/25/2013 11:49 AM, Dmitry S wrote:
>> >I am also confused by the numbers. What I see at the end of the article is
>> >"21.56 seconds, and the latest development version does it in 12.19", which is
>> >really a 43% improvement. (Which is really great too.)
>>
>> 21.56/12.19 is 1.77, i.e. a >75% improvement in speed.
>
> This is certainly misleading, is very easy to be confused with a time
> reduction of 75%, which one would expect to be 1/4 of the original time.
> :)
>

A doubling of the speed would be 100%, just saying.

Certainly you're technically correct about the 75% improvement in speed, but the units of speed for program execution is a little weird and unintuitive (Hz).   I've not run across anyone who says "my program got faster! It went from 0.05 Hz to 0.08 Hz!".  I think that's why people find it a little odd to talk about speed increase rather than time decrease.


On Sat, Jul 27, 2013 at 8:12 PM, torhu <no@spam.invalid> wrote:

> On 26.07.2013 01:15, Leandro Lucarella wrote:
>
>> Walter Bright, el 25 de July a las 14:27 me escribiste:
>>
>>> On 7/25/2013 11:49 AM, Dmitry S wrote:
>>> >I am also confused by the numbers. What I see at the end of the article
>>> is
>>> >"21.56 seconds, and the latest development version does it in 12.19",
>>> which is
>>> >really a 43% improvement. (Which is really great too.)
>>>
>>> 21.56/12.19 is 1.77, i.e. a >75% improvement in speed.
>>>
>>
>> This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :)
>>
>>
> A doubling of the speed would be 100%, just saying.
>

> I've not run across anyone who says "my program got
> faster! It went from 0.05 Hz to 0.08 Hz!".

People do say "my program does 10 X per second", though.

On Thursday, 25 July 2013 at 21:27:47 UTC, Walter Bright wrote:
> On 7/25/2013 11:49 AM, Dmitry S wrote:
>> I am also confused by the numbers. What I see at the end of the article is
>> "21.56 seconds, and the latest development version does it in 12.19", which is
>> really a 43% improvement. (Which is really great too.)
>
> 21.56/12.19 is 1.77, i.e. a >75% improvement in speed.
>
> A reduction in time would be the reciprocal of that.


Actually, it is a 43% speed improvement. 0.43*21.56 = 9.27s


So if it is 43% faster, it means it's reduced the time by 9.27s or, 21.56 - 9.27 = 12.28 seconds total.

Now, if we started at 12.28 seconds and it jumped to 21.56 then it would be 21.56/12.19 = 1.77 ==> 77% longer.

21.56/12.19 != 12.19/21.56.

The order matters.

To make it obvious. Suppose the running time is 20 seconds. You optimize it, it is 100% **faster**(= 1.0*20 = 20s seconds), then it takes 0 seconds(20 - 20).

Suppose the running time is 20 seconds, you screw it up, it takes 40 seconds, now it is 100% slower(1.0*20 = 20, and 20 + 20 = 40).

In both cases there is a difference of 20 seconds BUT they mean very different things.

A 20% increase is not calculated the same as a 20% decrease.

That is,

(A - B)/A != (A - B)/B.

The LHS is relative to A and the RHS is relative to B.

So

(21.56 - 12.19)/21.56 = 9.37/21.56 = 43%

or

1 - 12.19/21.56 = 1 - 0.57 = 0.43

To make the numbers simple,

20 second original, 10 second new.

How much faster is the new version? it is 10 seconds faster, or in percent, 1 - 10/20 = 0.5% (BUT if we started with 10 seconds then it would be increase of 100%)

The numbers are very close to the original, but not very close to 75%.


Basically you are calculating the percentage as if you slowed down the program... but it is not the same.

Another example will suffice:

Suppose you have 1000$. You lose 10% of it, or 100$. You now have 900$. You gain 10% of it, or 90$. You now have 990$! (Where did the 10$ go?)

This is why the stock market and economy is much worse than 2007 even though the numbers look the same. Easier: Suppose you have 1000$ loose 99% then gain 99%, you have only (1000*0.01)*1.99 = 10*1.99 = 19.9... no where near your original amount. (Even though the DIJA isn't a percentage this issue does creep into the calculation due to inflation and other factors)