[ANN] Lua 5.4.1 (rc1) now available

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

[ANN] Lua 5.4.1 (rc1) now available

Luiz Henrique de Figueiredo
Lua 5.4.1 (rc1) is now available for testing at
        http://www.lua.org/work/lua-5.4.1-rc1.tar.gz

The checksums are
        MD5 1d575faef1c907292edd79e7a2784d30  -
        SHA1 88961e7d4fda58ca2c6163938fd48db8880e803d  -

Lua 5.4.1 fixes all bugs listed in
        http://www.lua.org/bugs.html#5.4.0

Like all minor releases, this is strictly a bug-fix release: no new
features or improvements have been added.

Lua 5.4.1 also contains several internal improvements and
includes a revised reference manual:
        http://www.lua.org/work/doc/

The complete diffs from Lua 5.4.0 are available at
        http://www.lua.org/work/diffs-lua-5.4.0-lua-5.4.1.html
        http://www.lua.org/work/diffu-lua-5.4.0-lua-5.4.1.html

We thank everyone for their feedback on Lua 5.4 till now.

All feedback welcome. Thanks.
--lhf
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Luiz Henrique de Figueiredo
Lua 5.4.1 (rc1) is available for testing at
        http://www.lua.org/work/
Download it and give it a try.

Lua 5.4.1 fixes all bugs listed in
        http://www.lua.org/bugs.html#5.4.0

We have received no feedback on Lua 5.4.1. Does that mean that everything is
perfect with this release and that we can freeze it soon?

All feedback welcome. Thanks.
--lhf
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

John Belmonte
Regarding yield from __close, at least the documentation should be amended to note the limitation, as it does for __gc.

On Wed, Oct 7, 2020 at 9:20 AM Luiz Henrique de Figueiredo <[hidden email]> wrote:
Lua 5.4.1 (rc1) is available for testing at
        http://www.lua.org/work/
Download it and give it a try.

Lua 5.4.1 fixes all bugs listed in
        http://www.lua.org/bugs.html#5.4.0

We have received no feedback on Lua 5.4.1. Does that mean that everything is
perfect with this release and that we can freeze it soon?

All feedback welcome. Thanks.
--lhf
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Egor Skriptunoff-2
In reply to this post by Luiz Henrique de Figueiredo
On Wed, Oct 7, 2020 at 3:20 AM Luiz Henrique de Figueiredo wrote:
We have received no feedback on Lua 5.4.1.
Does that mean that everything is perfect?

Amortized cost of table insertion is O(n)
http://lua-users.org/lists/lua-l/2020-09/msg00178.html
It looks like a bug.
Although the manual promises nothing about Lua interpreter speed,
something like O(logn) is usually required for table operations.
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Soni "They/Them" L.
In reply to this post by John Belmonte


On 2020-10-07 9:21 a.m., John Belmonte wrote:
> Regarding yield from __close, at least the documentation should be
> amended to note the limitation, as it does for __gc.

If the documentation doesn't note it, then it can be changed in future
versions. see also: string uh match? gsub? not sure. that changed
somewhere between 5.3.x releases. (or was it 5.2.x?)

>
> On Wed, Oct 7, 2020 at 9:20 AM Luiz Henrique de Figueiredo
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>     Lua 5.4.1 (rc1) is available for testing at
>             http://www.lua.org/work/
>     Download it and give it a try.
>
>     Lua 5.4.1 fixes all bugs listed in
>             http://www.lua.org/bugs.html#5.4.0
>
>     We have received no feedback on Lua 5.4.1. Does that mean that
>     everything is
>     perfect with this release and that we can freeze it soon?
>
>     All feedback welcome. Thanks.
>     --lhf
>
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Gé Weijers
In reply to this post by Egor Skriptunoff-2
On Wed, Oct 7, 2020, 05:53 Egor Skriptunoff <[hidden email]> wrote:
On Wed, Oct 7, 2020 at 3:20 AM Luiz Henrique de Figueiredo wrote:
We have received no feedback on Lua 5.4.1.
Does that mean that everything is perfect?

Amortized cost of table insertion is O(n)
http://lua-users.org/lists/lua-l/2020-09/msg00178.html
It looks like a bug.
Although the manual promises nothing about Lua interpreter speed,
something like O(logn) is usually required for table operations.

Amortized cost of a single insert is O(1), and for 'n' operations is O(n). A single insert has a worst case cost of O(n) but the are very few of those. 

The strategy of doubling the size of a table each time you run out of space is essential for this behavior. You will only copy/rehash entries 2*n times worst case to grow a table to 'n' entries. 

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Roberto Ierusalimschy
In reply to this post by Soni "They/Them" L.
> > Regarding yield from __close, at least the documentation should be
> > amended to note the limitation, as it does for __gc.
>
> If the documentation doesn't note it, then it can be changed in future
> versions. see also: string uh match? gsub? not sure. that changed
> somewhere between 5.3.x releases. (or was it 5.2.x?)

Sure.

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Egor Skriptunoff-2
In reply to this post by Gé Weijers
On Wed, Oct 7, 2020 at 6:25 PM Gé Weijers wrote:
On Wed, Oct 7, 2020, 05:53 Egor Skriptunoff wrote:
Amortized cost of table insertion is O(n)

Amortized cost of a single insert is O(1), and for 'n' operations is O(n).

In some cases (see the link) the amortized cost of a single insert is O(n).

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Roberto Ierusalimschy
In reply to this post by Egor Skriptunoff-2
> Amortized cost of table insertion is O(n)
> http://lua-users.org/lists/lua-l/2020-09/msg00178.html
> It looks like a bug.
> Although the manual promises nothing about Lua interpreter speed,
> something like O(logn) is usually required for table operations.

I don't think it is wise to expect O(log n) as the worst case for table
operations. Most hash tables have a worst case O(n) for insertion and
retrieval, due to collisions.

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Egor Skriptunoff-2
On Wed, Oct 7, 2020 at 8:39 PM Roberto Ierusalimschy wrote:
> Amortized cost of table insertion is O(n)
> http://lua-users.org/lists/lua-l/2020-09/msg00178.html
> It looks like a bug.
> Although the manual promises nothing about Lua interpreter speed,
> something like O(logn) is usually required for table operations.

I don't think it is wise to expect O(log n) as the worst case for table
operations. Most hash tables have a worst case O(n) for insertion and
retrieval, due to collisions.

It is true that it is always possible to create a sequence of
table operations to exploit collisions in a hash table.

But the bug discussed here is not about collisions.
The keys in my example are the natural sequence of numbers 1,-1,2,-2,....
It is obviously NOT a maliciously crafted sequence to exploit hash table
collisions.

The bug is due to table rehashing might happen VERY often,
and each rehash costs O(n), hence the quadratic time complexity.
In a correct implementation it is wise to expect O(n) table operations done
before the next rehash happens.

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Roberto Ierusalimschy
> The bug is due to table rehashing might happen VERY often,
> and each rehash costs O(n), hence the quadratic time complexity.
> In a correct implementation it is wise to expect O(n) table operations done
> before the next rehash happens.

- Functionally, the behavior is exactly as expected.
- Hash tables can behave O(n) in worst-case situations.
- As you said, the manual says nothing about performance.

So, I don't see any bug here. (Of course, it would be better if we could
improve the perforance of tables.)

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Gé Weijers
On Wed, Oct 7, 2020 at 2:00 PM Roberto Ierusalimschy
<[hidden email]> wrote:
>
>
> So, I don't see any bug here. (Of course, it would be better if we could
> improve the perforance of tables.)

One problem is that this can create an opportunity for DOS attacks if
the numbers are under the control of an attacker.

Strings have a similar problem if the 'step' parameter of luaS_hash is
> 1, you can create enormous amounts of strings that all hash to the
same value. This works for strings of length 41 and up in Lua 5.4.
Inserting a million maliciously crafted strings into the key position
of a table takes close to two hours on my laptop.

The question is whether this kind of "pathological" behavior should be
considered a bug or not.


--

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Roberto Ierusalimschy
> Strings have a similar problem if the 'step' parameter of luaS_hash is
> > 1, you can create enormous amounts of strings that all hash to the
> same value. This works for strings of length 41 and up in Lua 5.4.
> Inserting a million maliciously crafted strings into the key position
> of a table takes close to two hours on my laptop.

We (the Lua team) were talking exactly about that. According to [1],
the goal of adding long strings in Lua was exactly to allow all string
hashes to use all characters. That was done (commit a4b96ce9), but for
some reason it was undone two months later (commit cfbe2333a).

[1] http://lua-users.org/lists/lua-l/2012-01/msg00196.html

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.4.1 (rc1) now available

Roberto Ierusalimschy
In reply to this post by Gé Weijers
> One problem is that this can create an opportunity for DOS attacks if
> the numbers are under the control of an attacker.

Not only the numbers! The code must explicitly insert some of them
in the table (a[i] = true) but "pseudo"-insert the others
(a[-i] = nil). That does not seem something that occurs often in
real code.

-- Roberto