Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Compact representations for arrays in Lua [pdf]

sol.sbc.org.br

Post reply on HN
Print view View original

11–20 of 22 posts

Re: Compact representations for arrays in Lua [pdf]

#11

Post by kragen »

debugnik wrote: post #10
kragen wrote: post #7

Earlier quoted context omitted.

You have no idea what 90% of their users are using. A lot of them aren't using LLVM or GCC. I'm pretty sure Roblox and WoW, for example, aren't normally compiled with LLVM or GCC. Whether those two games account for 99% of Lua's users or 0.001% depends on how you count, but no matter how you count, you have no idea.

Roblox accounts for 0% of stock Lua users, they run Luau. And many uses of Lua you come up with will be using LuaJIT or pinned to an older, possibly forked, Lua release. I'm not agreeing with the comment you replied to, just nitpicking.

You have good points.

Re: Compact representations for arrays in Lua [pdf]

#12

Post by ethan_smith »

Jyaif wrote: post #3

Jesus christ, 40% waste in arrays that can be solved by using `__attribute__((packed))`. Irresponsible of them of not advertising this as an option in luaconf.h

`__attribute__((packed))` wouldn't help here since the issue is about Lua's array/hash hybrid table design and memory allocation strategy, not C struct padding.

Re: Compact representations for arrays in Lua [pdf]

#13

Post by lifthrasiir »

ethan_smith wrote: post #12
Jyaif wrote: post #3

Jesus christ, 40% waste in arrays that can be solved by using `__attribute__((packed))`. Irresponsible of them of not advertising this as an option in luaconf.h

`__attribute__((packed))` wouldn't help here since the issue is about Lua's array/hash hybrid table design and memory allocation strategy, not C struct padding.

But it did help in the other way, in my reading of the paper [1]. So the OP is asking why this is not even an option on supported environments, and I too think that this is indeed a good question to ask.

[1] "Hugo Gualandi reported that just adding the gcc attribute __attribute__((packed)) to the definition of the structure TValue reduces its size from 16 to 9 bytes, without any sensible difference in performance."

Re: Compact representations for arrays in Lua [pdf]

#14

Post by nxobject »

Jyaif wrote: post #5
sfpotter wrote: post #4

Earlier quoted context omitted.

Here's the rest of that paragraph for you: "However, this attribute is a gcc extension not present in ISO C. Moreover, even in gcc it is not guaranteed to work [3]. As portability is a hallmark of Lua, this almost magical solution is a no-go."

[flagged]

The USP of Lua is the fact that's its easy to target embedded and microcontroller with funky/frozen toolchains -- that's why PUC-Rio Lua is written in C89. You're just as likely to have to use a "#pagma packed" as an attribute.

Re: Compact representations for arrays in Lua [pdf]

#15

Post by marhee »

I wonder, in reality, if a Lua program uses large (consecutive) arrays, its values will likely have the same type? At the very least it is a common use-case: large arrays of only strings, numbers etc. Wouldn’t it make sense to (also) optimize just for this case with a flag and a single type tag. Simple and it optimizes memory use for 98% of use cases?

Re: Compact representations for arrays in Lua [pdf]

#16

Post by tedunangst »

marhee wrote: post #15

I wonder, in reality, if a Lua program uses large (consecutive) arrays, its values will likely have the same type? At the very least it is a common use-case: large arrays of only strings, numbers etc. Wouldn’t it make sense to (also) optimize just for this case with a flag and a single type tag . Simple and it optimizes memory use for 98% of use cases?

This seems likely to create some inexplicable performance elbows where you have 1000 strings, but there's one code path that replaces one with a number, and now the whole array needs to be copied. Tracking that down won't be fun.

Re: Compact representations for arrays in Lua [pdf]

#17

Post by Jyaif »

marhee wrote: post #15

I wonder, in reality, if a Lua program uses large (consecutive) arrays, its values will likely have the same type? At the very least it is a common use-case: large arrays of only strings, numbers etc. Wouldn’t it make sense to (also) optimize just for this case with a flag and a single type tag . Simple and it optimizes memory use for 98% of use cases?

It makes a lot of sense, and but then you have two code paths for tables.

The Lua folks want a simple codebase, so they (knowingly) leave a lot of performance on the table in favor of simplicity.

Re: Compact representations for arrays in Lua [pdf]

#18

Post by ufo »

marhee wrote: post #15

I wonder, in reality, if a Lua program uses large (consecutive) arrays, its values will likely have the same type? At the very least it is a common use-case: large arrays of only strings, numbers etc. Wouldn’t it make sense to (also) optimize just for this case with a flag and a single type tag . Simple and it optimizes memory use for 98% of use cases?

The main catch is that if the optimization guesses wrong and a different type is inserted into the table afterwards, then it would incurr an O(n) operation to transfer all the data to a deoptimized table.

Another caveat is that Lua can have more than one internal representation for the same type, and those have different type tag variants. For instance: strings can be represented internally as either short or long strings; Functions can be Lua closures, C closures, or perhaps even an object with a __call metamethod; Objects can be either tables or userdata.

Re: Compact representations for arrays in Lua [pdf]

#19

Post by ufo »

Jyaif wrote: post #17
marhee wrote: post #15

I wonder, in reality, if a Lua program uses large (consecutive) arrays, its values will likely have the same type? At the very least it is a common use-case: large arrays of only strings, numbers etc. Wouldn’t it make sense to (also) optimize just for this case with a flag and a single type tag . Simple and it optimizes memory use for 98% of use cases?

It makes a lot of sense, and but then you have two code paths for tables. The Lua folks want a simple codebase, so they (knowingly) leave a lot of performance on the table in favor of simplicity.

For what it's worth, there are already two code paths for tables. The array part is stored separately from the hash table part.

Re: Compact representations for arrays in Lua [pdf]

#20

Post by hugomg »

lifthrasiir wrote: post #13
ethan_smith wrote: post #12

Earlier quoted context omitted.

`__attribute__((packed))` wouldn't help here since the issue is about Lua's array/hash hybrid table design and memory allocation strategy, not C struct padding.

But it did help in the other way, in my reading of the paper [1]. So the OP is asking why this is not even an option on supported environments, and I too think that this is indeed a good question to ask. [1] "Hugo Gualandi reported that just adding the gcc attribute __attribute__((packed)) to the definition of the structure TValue reduces its size from 16 to 9 bytes, without any sensible difference in performance."

We figured that it wasn't worth dealing with the hassle of unaligned addresses because the more portable alternatives worked just as well.
Post reply on HN