richardhundt
commented
10 years ago On 4/6/14 11:19 PM, romix wrote:
This is just an idea.
"struct" and "fields" allow for defining types that have a fixed structure. May be this information can be used for more efficient access to these objects both in terms of memory usage and performance?
The following optimizations could be potentially possible:
1) More efficient layout of objects in memory. In theory, fields could be mapped to equivalent of a C-struct with corresponding fields.
Well, if the values are not cdata types then that wouldn't work.
Or at least to an Lua-table which has only array elements. Each field name gets mapped to an array-index. obj.fieldX becomes obj[idX]. This could be more memory efficient than hash-table based storage of those fields.
I've experimented with this kind of thing. So you do save on space.
However it also means that these structs respond to both obj[1] as
well as obj.fieldX, and saying the latter is an indirection: you need
a reverse mapping from fieldX to the slot index. So you can't really
get rid of the hash lookup for fieldX - it either references the
member value directly, or it references the slot which references the value.
What's more, there's also no guarantee that the members are going to be
actually stored in the "array part" of the table. That depends on the
order in which the fields are initialized. If fieldX was slot 1 and
fieldY slot 2, then setting fieldY first will make the underlying
table use the hash part anyway, so you don't gain anything.
The thing is that Lua's tables are fast because the don't re-hash the string every time. They use pointer hashing - which is essentially integer hashing. Strings are interned (well except for short strings, but that's an implementation detail).
I've had cases where using LuaJIT's tables are faster than C structs. It does some badass optimizations.
2) (1) is also somewhat similar to Python's named tuples: https://docs.python.org/2/library/collections.html#collections.namedtuple They may use less memory and be accessed more efficiently.
3) May be LuaJIT/compiler may make use of the fact that the structure of objects does not change during run-time? This information could be used e.g. for copy propagation and some other optimizations... I'm not sure though that LuaJIT is able on its own to understand that structure of objects(i.e. tables) is fixed (this needs to be tested yet). Eventually, it may require some help, e.g. some hints ( a-la PyPy JIT hints).
LuaJIT has a TDUP instruction. What the compiler does is store the constant parts tables in the bytecode, and then duplicate these instead of reconstructing them. So if you had
t = { answer = 42, greet = function() print("Hi") end }Then the {answer = 42} part is constant, whereas the function is a GC
object so needs to be attached after the TDUP. This definitely speeds
things up, but has limited use for our case, because struct definitions
have other tables as their field values (i.e. the type).
It's not like this stuff is actually slow, right?
Note: Overall, it would be interesting to understand if a compiler or runtime of Shine may somehow provide hints to LuaJIT to enable better optimizations. I understand that currently LuaJIT does not provide support for this. But if it would, what could be done? This kind of input could interesting for Mile Pall to convince him that supporting some sort of hints could be very valuable.
It's been suggested before on the mailing list to make LuaJIT more
friendly as a compilation target for other languages. I can't remember
Mike's response exactly, but it didn't seem to be a goal of his. It's
actually hard to erase the underlying Lua semantics. For instance, in
many languages 0 and the empty string evaluate to false. Not so in
Lua. So if you wanted that, you'd have to wrap every boolean context
evaluation in your own function call.
If your language has mutable strings, then you'd need to replace the native string type and half the VM instructions become useless to you. Then there's the GC. If you wanted to have real low level classes and objects (not based on tables, but language primitives as in Java), then you'd pretty much need to do your own tracing and garbage collection because you don't have mark and sweep hooks.
So it's actually a fairly non-trivial job to make the LuaJIT VM generic in this way.
4) Since Lua is very dynamic, I can imagine that Shine compiler could potentially only statically make use of the fixed layout only in the scope where a variable was declared. But when it gets passed to a different function (or another scope, in general), then this statically known information is most likely lost (unless some sort of very clever escape analysis is used). I don't know if LuaJIT can do any better using traces and propagating this information along traces.
Then struct declarations would need to be added to the language, and
not be part of a library (they're just functions). Right now the
compiler just sees a function call.
An interesting idea would definitely be to integrate the FFI more into the language so that C declarations are parsed directly, but with Shine syntax. I've toyed with this too:
struct Buffer
size is size_t
data is char*
endYou'd then get the ffi.cdef stuff done for you behind the scenes.
This gets hairy though, because what does char* mean in the rest of
the language? Can I call it? What if I want to cast it? If casts have
their own syntax, what if I try to cast a table? Tricky stuff.
Right now the fact that you need to pass strings to ffi.cdef and do
all the operations via a library makes it clear that you're dealing with
stuff that's external to the language (i.e. the foreign in ffi).
As I said, these are just some ideas. I'm not sure how feasible they are and if something like this is possible at all.
What do you think?
Sure, all good ideas. For now though, I feel that Shine is squeezing about as much out of LuaJIT as a sugar language can hope to, without going down a complexity rabbit hole.
romix
This is just an idea.
"struct" and "fields" allow for defining types that have a fixed structure. May be this information can be used for more efficient access to these objects both in terms of memory usage and performance?
The following optimizations could be potentially possible:
1) More efficient layout of objects in memory. In theory, fields could be mapped to equivalent of a C-struct with corresponding fields.
Or at least to an Lua-table which has only array elements. Each field name gets mapped to an array-index. obj.fieldX becomes obj[idX]. This could be more memory efficient than hash-table based storage of those fields.
2) (1) is also somewhat similar to Python's named tuples: https://docs.python.org/2/library/collections.html#collections.namedtuple They may use less memory and be accessed more efficiently.
3) May be LuaJIT/compiler may make use of the fact that the structure of objects does not change during run-time? This information could be used e.g. for copy propagation and some other optimizations... I'm not sure though that LuaJIT is able on its own to understand that structure of objects(i.e. tables) is fixed (this needs to be tested yet). Eventually, it may require some help, e.g. some hints ( a-la PyPy JIT hints).
Note: Overall, it would be interesting to understand if a compiler or runtime of Shine may somehow provide hints to LuaJIT to enable better optimizations. I understand that currently LuaJIT does not provide support for this. But if it would, what could be done? This kind of input could interesting for Mile Pall to convince him that supporting some sort of hints could be very valuable.
4) Since Lua is very dynamic, I can imagine that Shine compiler could potentially only statically make use of the fixed layout only in the scope where a variable was declared. But when it gets passed to a different function (or another scope, in general), then this statically known information is most likely lost (unless some sort of very clever escape analysis is used). I don't know if LuaJIT can do any better using traces and propagating this information along traces.
As I said, these are just some ideas. I'm not sure how feasible they are and if something like this is possible at all.
What do you think?