Tru Count - Lua Core Patch
H. Diedrich
I'll put a current version up at http://eonblast.com/trucount .
Thanks,
Henning
H. Diedrich
Thanks a lot for looking into it. Maybe you find time to go further and
please keep telling me your impression!
Can I point out my motivation:
[At this point, '$' is the tru count operator in the patch]
> "$ should be used instead of '#' on tables in almost all cases",
because arrays containing non-numeric keys aren't rear.
The reason is that for strict arrays $ == #. And $ is faster (must be
faster) than #. If you apply the patch, it incurs a minuscule penalty
during any array set, insert or remove. You are paying that with the
patch, no matter if you ever use $. That is the weak point about it. But
if you have it patched, using $ instead of # for strict arrays is going
to return faster, even though '#' on strict arrays is already fast.
Caveat: no benchmarks yet, I am writing based on code inspection.
> I also don't think that $ result is of any use for an array with
holes. In that case the only way to have length is to take care of it
manually, keeping it in 't.n' or having a vector library for that.
I did not bring across then what '$' is all about. This case. It is
equivalent to taking care of it manually, or, traversing manually when
needed.
What made you think otherwise, or, where would you have needed the clear
statement telling you so?
Or are you talking about the '#+1' for a safe insertion place?
Thanks,
Henning
steve donovan
> From Roberto's point of view (and this is stated explictly for the somewhat
> related function maxn in the reference manual) you could write:
>
> function count(t) local n=0 for k in pairs(t) do n=n+1 end return n end
>
> Sure, that's O(n), but in 99.9% of all programs this won't be the bottleneck,
That would be my concern - that tracking the true count of a table is
usually not a priority.
It is also a flawed proxy measure for 'holiness' because the true
count also counts string keys. If people are careful not to tag their
arrays (a common Lua strategy), then it is a fast way to tell, but
there is an 'if'.
If we count all sorts of things, number of integer keys, etc, etc then
each count adds another 4 bytes to the table structure. That can
affect the scalability of programs that need to create a _lot_ of
tables.
Appropriate data types still feel like the way to go, if one wants
particular semantics.
steve d.
Henning Diedrich
On Jan 18, 7:14 am, steve donovan <steve.j.dono...@gmail.com> wrote:
> That would be my concern - that tracking the true count of a table is
> usually not a priority.
use really minimal and my impression is that you want to know the true
count of your tables quite frequently. But that's only my view.
> It is also a flawed proxy measure for 'holiness' because the true
> count also counts string keys.
problem but could obviously serve as a blueprint to address it,
nothing more.
> If we count all sorts of things, number of integer keys, etc, etc
> then each count adds another 4 bytes to the table structure. That can
> affect the scalability of programs that need to create a _lot_ of
> tables.
but not bare-bone type slim.
Regardless, if one uses a million tables, it will of course make a
difference!
I would not in the first place but again that's only me. Is it common?
> Appropriate data types still feel like the way to go
Best,
Henning
Dirk Laurie
>
> If we count all sorts of things, number of integer keys, etc, etc then
> each count adds another 4 bytes to the table structure. That can
> affect the scalability of programs that need to create a _lot_ of
> tables.
>
integers. This is a power of 2. Do you think that is a coincidence,
or a carefully crafted design?
Moreover, some of the pointer fields imply the existence of objects
that are unique to each table. Total overheads is more like 64 bytes
per table. Increasing that by four size_t's is 25% for an empty table,
20% for a table with two Numbers (e.g. 2D points).
These percentage do not frighten me too much.
> Appropriate data types still feel like the way to go, if one wants
> particular semantics.
>
If you can suggest a way to avoid proxy tables, I'll agree unreservedly.
Although — the overrides of __newindex and __len are much easier if a
core patch is in effect that makes len(), maxn() and count() available.
Dirk
Axel Kittenberger
application it does matter, also for gaming industry. Lua went lengths
to keep table smalls using some fields bit by bit. To add aditional 32
or 64 bits needs a real convincing reason. Is calculating the length
on request so expensive it justifies a 25% larger memory footprint? In
my opinion We're back to datatypes/metatables to track them only for
tables where needed.
Axel Kittenberger
application it does matter, also for gaming industry. Lua went lengths
to keep table smalls using some fields bit by bit. To add aditional 32
or 64 bits needs a real convincing reason. Is calculating the length
on request so expensive it justifies a 25% larger memory footprint? In
my opinion We're back to datatypes/metatables to track them only for
tables where needed.
Henning Diedrich
On Jan 18, 9:20 am, Dirk Laurie <d...@sun.ac.za> wrote:
> Current Table struct has size 32 bytes assuming 4-byte pointer and
> integers. This is a power of 2. Do you think that is a coincidence,
> or a carefully crafted design?
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked
...
typedef struct Table {
CommonHeader;
lu_byte flags; /* 1<<p means tagmethod(p) is not present */
lu_byte lsizenode; /* log2 of size of `node' array */
struct Table *metatable;
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
GCObject *gclist;
int sizearray; /* size of `array' array */
} Table;
> Although — the overrides of __newindex and __len are much easier if a
> core patch is in effect that makes len(), maxn() and count() available.
with them. Non-space optimized in the beginning.
Henning Diedrich
> I dont like increasing the memory usage for every table. For my
> application it does matter, also for gaming industry. Lua went lengths
> to keep table smalls using some fields bit by bit. To add aditional 32
> or 64 bits needs a real convincing reason. Is calculating the length
> on request so expensive it justifies a 25% larger memory footprint?
expressed by the list.
So in anticipation of the even stronger response from the Lua
community on the matter, I should yield.
Again, please take into account that repeated length() calls on big
tables will trigger traversion again and again and make it effectively
useless.
But I very much like the requirement that no memory should be wasted.
What about this: a separate low level list that has entries only for
those tables on which ever there was a length/size/etc call. Where the
live counters kick in only after one of these calls happened for the
first time (and then is not stoppable). The first time around,
traversing is used to get the numbers. Any time after that, direct
counter value look up takes place.
That's complicated but matches the Lua table implementation in
versatility and effort.
But again, where do you need so many tables that some overhead has
consequences?
Henning
Henning Diedrich
> that are unique to each table. Total overheads is more like 64 bytes
> per table. Increasing that by four size_t's is 25% for an empty table,
> 20% for a table with two Numbers (e.g. 2D points).
be seen, 'sizearray' also is only an int.
Dirk Laurie
> I dont like increasing the memory usage for every table.
> a 25% larger memory footprint?
but extra memory, and an extra prefix operator, needs more motivation
than merely saving a little time now and then.
The "vanity" module could still contain all those functions, though,
even if they don't exploit core patches, so the user can simply put
vanity.truecount(t)
which would set getmetatable(t).__len to vanity.count, creating
a metatable for t if none is available.
> my opinion We're back to datatypes/metatables to track them only for
> tables where needed.
If we are going to code the module in C, lists, stacks, queues, deques,
heaps and arrays are better implemented as userdata than as
specializations of tables. There is all of the C++ template library
to borrow the algorithms from.
The moment you take away the feature that any value can be a key, the
need to use a table vanishes too. Sets are debatable; I think the
table wins, but only just. Multisets give a clear case in favour of
a table.
Dirk
Axel Kittenberger
>> tables where needed.
> If we are going to code the module in C, lists, stacks, queues, deques,
> heaps and arrays are better implemented as userdata than as
> specializations of tables. There is all of the C++ template library
> to borrow the algorithms from.
I would not do that, first there is the License issue, second the C++
template library is a pain to read! If you ever open it you will
wonder. Third its all so standard today, you can look them up in any
teaching book. Okay, real implementations are always a tad different
than the teached stuff. But IMHO its better to specialize from
standard implementation than to borrow from an other language.
> The moment you take away the feature that any value can be a key, the
> need to use a table vanishes too. Sets are debatable; I think the
> table wins, but only just. Multisets give a clear case in favour of
> a table.
Uhh userdata. This might be a large patch to the core, but how about
changing userdata and table into one object "tableish". I'm thinking
of something like the inodes in the Linux kernel. Every node has a set
of function pointers that define its behaviour. So yes calling a
function pointer is a tad less than the current preprocessor macros,
but that might be argueable for the benifit. A set of function pointer
per "node" is too expensive, but we could have groups/prototypes. The
current hash+array implementation is then one, the default "tableish".
Userdata is too "tableish". A hash+chained list might be a another
one, etc. This would actually reduce the number of basic types to Lua,
that would be very Lua-ish minimalist, wouldn't it? Also this would
allow C-extensions to add their own basic types. But well, it might be
done with current Userdata tough...
Dirk Laurie
>
> Uhh userdata. This might be a large patch to the core, but how about
> changing userdata and table into one object "tableish".
>
in ch 28, p259-267 in PiL2. Not that I claim to understand that
chapter. Yet.
> Every node has a set of function pointers that define its behaviour.
A metatable, in other words?
Dirk
Axel Kittenberger
>> changing userdata and table into one object "tableish".
>>
> Nononono, not a core patch. A separate C module. As described
> in ch 28, p259-267 in PiL2. Not that I claim to understand that
> chapter. Yet.
>
>> Every node has a set of function pointers that define its behaviour.
> A metatable, in other words?
A metatable is exactly a table. When supposing a mechanism more basic
in which the ltable.c and userdata is merly one instance of it, it
cannot be metatables.
Its all still a vague idea, as new thoughts can break easy on the
beginning. Why are tables not the same as userdata?
Henning Diedrich
> On Tue, Jan 18, 2011 at 11:13:01AM +0200, Axel Kittenberger wrote:
> > a 25% larger memory footprint?
use of tables that I thought was normal, this could be negligible.
My objective would be, to make Lua smoother, so yes, I would
accept a penalty and balance it against the likeliness of coder
mistakes, which is a very abstract, but common view. (The
main Python claim usually, and also Erlang's in a way).
> OK, you are right. Henning's patch is so neat, I wish I had done it,
> but extra memory, and an extra prefix operator,
absolutely
separate from all else, and backward-compatible. It certainly needs
not stay that way.
> needs more motivation
> than merely saving a little time now and then.
just very different.
What would you need so many tables for that the some bytes per table
weigh in?
But anyway, I can appreciate the premise that the cost must be close
to 0.
I am really curious what dropping the key-shift could effect. While
that is not directly related, the form of 'live counting' of that
patch would probably help with that, too.
> The "vanity" module could still contain all those functions, though,
> even if they don't exploit core patches, so the user can simply put
> vanity.truecount(t)
> which would set getmetatable(t).__len to vanity.count, creating
> a metatable for t if none is available.
convinced yet that a good solution can get around it.
> If we are going to code the module in C, lists, stacks, queues, deques,
> heaps and arrays
are better implemented as userdata than as
> specializations of tables. There is all of the C++ template library
> to borrow the algorithms from.
Henning
Henning Diedrich
> When supposing a mechanism more basic
> in which the ltable.c and userdata is merly one instance of it
but to assign it as if it was metatable? Or what should the common
aspect of the two be?
Thanks,
Henning
steve donovan
> Why do you want to do that? To be able to roam freely on the userdata
> but to assign it as if it was metatable? Or what should the common
> aspect of the two be?
They really are very different animals - the inner structure of
userdata is arbitrary and managed by C/C++. They can be given
equivalent _interfaces_ using the metatable mechanism but they are
otherwise opaque.
(OK, one can do evil things. Like adding new methods to Lua file
objects by poking them into the (shared) file object metatable. I have
made a New Year's resolution not to do such things.)
steve d.
Axel Kittenberger
> but to assign it as if it was metatable? Or what should the common
> aspect of the two be?
The question, why are tables not "user"data?
Am I'm overlooking something or is this pure paradigmsn for some
operations on tables to be optimized by inlining the setter/getter
routines?
They are a projections:
k --> v, k € K, K being finite group. and for tables k € K v is not nil.
Axel Kittenberger
> userdata is arbitrary and managed by C/C++. They can be given
> equivalent _interfaces_ using the metatable mechanism but they are
> otherwise opaque.
For the rest of the Lua core the current table data structure is
abitrary and managed by C code :-)
Henning Diedrich
This might be a large patch to the core, but how about changing userdata and table into one object "tableish". I'm thinking of something like the inodes in the Linux kernel.
I think that's too tough. If you mean that this can be passed around inside the core as a kind-of polymorphic tableish object (union). That could easily require too many checks for type (table or userdata) to be viable. The core is not OO after all ...
Henning
Henning Diedrich
Leo Razoumov
Actually, I do not see how one gets 25% overhead.
On a 32-bit system size_t is 4 bytes, thus, overhead of the counter (4
bytes) is compared to sizeof(struct Table)=32 and is 12.5%
On a 64-bit system size_t is 8 bytes but sizeof(struct Table) is
probably 64 (with proper alignment and holes due to standalone bytes).
Overhead is again around 12.5%.
Also 64-bit systems typically have much more memory to begin with and
this tiny overhead thing is mute.
--Leo--
Henning Diedrich
> > From Roberto's point of view (and this is stated explictly for the somewhat
> > related function maxn in the reference manual) you could write:
>
> > function count(t) local n=0 for k in pairs(t) do n=n+1 end return n end
>
> > Sure, that's O(n), but in 99.9% of all programs this won't be the bottleneck,
> That would be my concern - that tracking the true count of a table is
> usually not a priority.
out if the table mechanism could be sped up! At the cost of a small
penalty.
I thought having the true count available at O(1) could be quite cool,
too.
But yet if you don't, my question would currently be -- now that it
looks like it works -- if it can serve to speed up the entire table
mechanism.
I would not be surprised, because after all the table, as it is, is
also something that probably grew into what it is now and I am only
trying to gain some perspective of the potential of refactoring. Could
still be 'none'! That's what I am trying to find out.
The most obvious place is the rehash, where it counts array and hash
elements, every time it re-hashes.
Best,
Henning
Henning Diedrich
> A separate C module. As described
> in ch 28, p259-267 in PiL2.
core for answers, maybe at some point that can be forked into a
module, which I would find more attractive for a couple of reasons,
too.
Henning
Henning Diedrich
> in ch 28, p259-267 in PiL2. Not that I claim to understand that
> chapter. Yet.
are quoting just this, as in PiL 1 chapter 26? Or is there something
else to it (no matter if statically or dynamically linked):
File ../src/hello.lua:
----------------------
hellolib.hello()
File src/hello.c:
-----------------
#include <stdio.h>
#include "lauxlib.h"
static int hello(lua_State *L) {
printf("Hello World!\n");
return 1;
}
static const struct luaL_Reg hellolib [] = {
{ "hello", hello }, /* registering the function */
{ NULL, NULL }
};
LUALIB_API int luaopen_hellolib (lua_State *L) {
luaL_register(L, "hellolib", hellolib); /* registering the module */
return 1;
}
File src/hello.h:
-----------------
#include "lua.h"
#define HELLO_LIBNAME "hellolib"
LUALIB_API int (luaopen_hellolib) (lua_State *L);
Extend file src/linit.c:
------------------------
...
#include "lauxlib.h"
#include "hello.h" /* add */
...
static const luaL_Reg lualibs[] = {
...
{"hellolib", luaopen_hellolib}, /* add */
{NULL, NULL}
...
Extend src/Makefile:
--------------------
...
LIB_O= lauxlib.o lbaselib.o ldblib.o liolib.o lmathlib.o loslib.o
ltablib.o \
lstrlib.o loadlib.o linit.o hello.o # add
...
hello.o: hello.c # add
# (end of Makefile)
Build & Run
-----------
Build Lua from ../src/ folder, e.g. sudo make
Run src/lua hello.lua
steve donovan
> I think I have PiL 1. Is a separate module in the sense of what you
> are quoting just this, as in PiL 1 chapter 26? Or is there something
> else to it (no matter if statically or dynamically linked):
Yes, it really is that simple - piece of cake!
I have an idea for a project[1] which automates this process; you can
build Lua and specify what extra modules you want to include,
particularly standard useful stuff like LuaFileSystem and LuaSocket
[2]. (Or exclude, like if you wanted an embedded Lua that did not have
some standard libraries.)
Would probably be an excuse to exercise Lake, which is yet another
build engine [3]
steve d.
[1] how many nightmares have begun this way?
[2] not a piece of cake - there's Lua code involved which has to be
wrapped in C.
[3] https://github.com/stevedonovan/Lake
Henning Diedrich
> particularly standard useful stuff like LuaFileSystem and LuaSocket
Seriously thought, what about rocks? Someone dissed it horribly a bit
ago but I find it very valuable?
And on the other hand, the problems Rocks run into ... particularly
pathes ... I would really not want to go through that ...
> Would probably be an excuse to exercise Lake
And is it even somewhat circular? Lake could already make good use of
a packaged filesystem as I see it there on the github pages ... :-o
What would you deliver as initial package? Or am I not seeing the very
point you are making?
Henning
steve donovan
> Seriously thought, what about rocks? Someone dissed it horribly a bit
> ago but I find it very valuable?
LuaRocks is good for delivering dynamically loaded modules, but not (I
think) for custom Lua builds.
> Which would require you to have Lua first to then build a better Lua?
Well, I assume that people already have Lua - easy enough, just
apt-get or Lua for Windows. But people sometimes need to build a
custom Lua, e.g. cross-compiling for ARM, etc.
> And is it even somewhat circular? Lake could already make good use of
> a packaged filesystem as I see it there on the github pages ... :-o
I'd like to see what you see ;)
> What would you deliver as initial package? Or am I not seeing the very
> point you are making?
The way I see it, you start off with a binary Lua, plus lfs and lake.
LuaBuild (to give it a name) would then grab the Lua source (and other
packages, if requested) and build a custom Lua that has (say)
LuaFileSystem statically included. It would patch linit.c and adjust
the build accordingly. It would know how to apply common patches like
ltokens or LNUM.
Why Lake as a starting point - well you know how awkward Make is for
tricky jobs. A lakefile can build a program using either GCC or MSVC
on Windows, and is basically a Lua script, so it can do clever stuff
without depending on the shell environment like Make does. Not a new
idea (there's CMake) but useful for this current task.
However, we all know the temptations of _too many projects_. I can't
afford to neglect things like Penlight which people actually use. And
my particular itch at the moment is Orbiter, hoping to get that out
this weekend.
steve d.
Henning Diedrich
> On Thu, Jan 20, 2011 at 1:04 PM, Henning Diedrich <hd2...@eonblast.com> wrote:
> > Seriously thought, what about rocks? Someone dissed it horribly a bit
> > ago but I find it very valuable?
>
> LuaRocks is good for delivering dynamically loaded modules, but not (I
> think) for custom Lua builds.
line with what I am looking for.
> > And is it even somewhat circular? Lake could already make good use of
> > a packaged filesystem as I see it there on the github pages ... :-o
>
> I'd like to see what you see ;)
before you can use Lake which would exactly be a case where a
customized Lua, including the filesystem, would come in handy.
> The way I see it, you start off with a binary Lua, plus lfs and lake.
and tight.
> LuaBuild (to give it a name)
> LuaFileSystem statically included. It would patch linit.c and adjust
> the build accordingly. It would know how to apply common patches like
> ltokens or LNUM.
> Why Lake as a starting point -
as a native make system --- you could even hack it if you needed
something very special.
+ portability!
Henning
steve donovan
> So it's not for an easy start into Lua, but for bundling it up nice
> and tight.
That's exactly right. Not for newbies.
> Because you made it? Which is fair. But I also think it's appropriate
> as a native make system --- you could even hack it if you needed
> something very special.
This is true - could be a Lua script which patched things like
luaconf.h, linit.c and the current makefile.
_That_ would be an entertaining rainy Sunday's work, no?[1]
steve d.
[1] yes, I know. I should get out more if this is my idea of fun.
Henning Diedrich
what's your take on the exactly 32 byte the table struct seems to take. Is that of significance?
Thanks,
Henning
Henning Diedrich
> [1] yes, I know. I should get out more if this is my idea of fun.
definition of fun :-D
Leo Razoumov
>
> Hi Leo,
>
> what's your take on the exactly 32 byte the table struct seems to take. Is
> that of significance?
>
> Thanks,
> Henning
>
Henning,
it is 32 bytes only on a 32-bit architecture. On x86_64 machine it is
64 bytes. But it is still power of two. Possibly helps to optimize
memory allocator.
I attached below a little module (for Lua-5.1.4) that you can use to
see exactly what is sizeof(Table) in your specific case.
Adopt Makefile accordingly.
--Leo--
Henning Diedrich
> I attached below a little module (for Lua-5.1.4) that you can use to
> see exactly what is sizeof(Table) in your specific case.
> Adopt Makefile accordingly.
of 32
In case someone wants to verify, Leo provides, in his post above, a
miniature C module that can be built as dynamic library, then used by
| require("Lsizeof"); print(Lsizeof.table()) |. Note that the sizeof
that it will report is dependent on the lobject.h that it is compiled
with and will not automatically reflect the flavor/version/patch of
Lua that you run these Lua lines with. The size is burned in at
compile time, which doesn't diminish its usefulness.
And so we see the table header's size being increased by 12.5%
currently, as Leo predicted and I am still looking at the Table
structure to see if I can reuse of of the existing pointers or
counters.
I must admit that I still can't see a use case where that matters. You
would usually not have empty tables but tables with something in, so
the relative increase is way smaller, maybe 1%. Each node in the table
is 28 bytes (on 32 bit systems. Measured extending Leo's Lsizeof). So
you have a table with 10 entries, even just integers, not strings, you
have sth. like 300 bytes there, and the increase of size is going
towards ~1% (312 -> 316 -> 1.28%). Have a table of 100 entries and
it's ~0.1% etc
Obviously, the size increase is less relevant exactly when O(1)
matters most: with bigger tables.
{And the ultimate finger breaker 'L-s-i-z-e-o-f'. I find sizeof hard
to type, but this is even better}
But if you have only small tables, won't that be the case when you
also have enough memory left?
Anyway, thanks for insisting there, Leo,
Henning
Henning Diedrich
> see exactly what is sizeof(Table) in your specific case.
> Adopt Makefile accordingly.
in the LFLAGS.
SHELL=/bin/sh
.SECONDARY: # keep intermediary files
CC = gcc
INC=
CFLAGS = -O2 -Wall -DLUA_USE_MACOSX $(INC)
LIBS= -lm -lc -lreadline
LFLAGS= -bundle -undefined dynamic_lookup
all: Lsizeof.so
clean:
-rm -f *.so
-rm -f *.o
Lsizeof.o: Lsizeof.c lobject.h llimits.h
$(CC) $(CFLAGS) -c $< -o $@
%.o: %.c
$(CC) $(CFLAGS) -c $< -o $@
%.so: %.o
$(LD) $(LFLAGS) -o $@ $(filter %.o,$^) $(filter %.a,$^) $(LIBS)
#EoF
Leo Razoumov
> Thanks! So --- the end of guessing, currently that is 36 bytes instead
> of 32
Interesting! On Linux x86 32bits with Lua-5.1.4 Lsizeof.table()
returns 32. I guess that 36 bytes you quote is on MAC OS X.
> I must admit that I still can't see a use case where that matters. You
> would usually not have empty tables but tables with something in, so
> the relative increase is way smaller, maybe 1%.
IMHO, the overhead of this extra counter does not matter, although I
would like to see a realistic example to the contrary.
> Anyway, thanks for insisting there, Leo,
> Henning
Insisting is my forte:-)
--Leo--
Henning Diedrich
On Fri, Jan 21, 2011 at 01:45, Henning Diedrich <hd2...@eonblast.com> wrote:Thanks! So --- the end of guessing, currently that is 36 bytes instead of 32Interesting! On Linux x86 32bits with Lua-5.1.4 Lsizeof.table() returns 32. I guess that 36 bytes you quote is on MAC OS X.
Henning