lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


You should note that I have already worked on enabling the reuse of IEEE 64-bit NaN values for encoding almost all Lua values, including short strings (up to 6 bytes).

And in that case there's never any need to allocate any extra buffer: short strings are just copied by value and no longer by reference. And this considerably boosts the speed of various Lua libraries using very short strings, including notably the Lua parser and compiler itself, and reduces a lot the stress on the garbage collector (note that these short string no longer any any complex hashing for use as keys in tables). This also applies to most integer keys, that can be represented using IEEE 64-bit doubles; and I still allow special floatting points, notably denormal values, sized zeroes, the two infinite values, and large ranges of NaN values (signaling and non-signaling, keeping also their sign bit; only one half the non-signaling NaN values are used to represent all other objects, including other strings and reference types, where a smaller "object identifier" is used to replace 64-bit pointers, with just one constraint: a small alignment constraint which also offers advantages.)

This is a complete success (and already in production: it passed all existing Lua self-tests). This currently targets 64-bit platforms

A test using IEEE 32-bit floats is in progress for targetting 32-bit platforms but it adds a constraint in the maximum size of the user memory space for each object type, however for most practical cases, the limit is not reached, and I still get a detectable improvement in terms of speed, but the code is still not optimal and some worst cases are still occuring, where performance could be a bit slower; however short strings encoded as values and not as references are smaller: only 2 bytes at most for now, but I think I could encode some interesting ranges of 3-byte strings notably ASCII only, and some 4-byte strings using a subset of ASCII such as digits, letters, dot and minus-hypen, and another subset for hexadecimal strings (this test code is not finished). This 32-bit code is much more tricky, even if I want it to have a general purpose for most practical uses.

Another thing that I have improved is the allocator of objects: it uses separate memory pools for short objects depending on their size.

The next thing I will work on is data compression, notably for Unicode text (basically the code will be able to choose between several internal UTF forms; still string values in Lua will NOT be restricted to be only valid text in a valid UTF form; however I need to reduce the scanner time to detect strings that are not in any known valid UTF so that I fallback fast to a generic form using unconstrained byte values, that will not be compressed/decompressed, and some tuning to design the limit, which should probably not exceed 4 kibibytes, i.e. a single memory page, and may be a autotuning algorithm that will keep some statistics on string sizes, and possibly a way to allow the garbage collector to dynamically reencode/compress/decompress some strings that have higher frequencies of use; also caches will be using weak-referenced pages from segregated pools of memory).

Also now I no longer use at all the basic hash tables implemented in core Lua: ALL tables are now using B-trees, without any segregation between indexed part and hash part: they are much more efficient, including for the garbage collection, use less memory, and have much better locality (i.e. faster in caches); undesirable side effects of the existing segregation is unacceptable and makes the code very fragile (and easily attackable). The pairs() and ipairs() iterators are still working as expected. I am still working on it in terms of security (i.e. avoid attacks on caches, because it still uses a basic LRU strategy, for which I am already aware that it is attackable: I will redesign the caches using security domains, so that no concurrent thread can flush the cache used by other critical threads and detect some side channels: the caches will be also using pools). I'm also working on designing several storage formats for pages in the B-tree, and tuning them (notably pages in the B-tree contain BOTH the keys and values, except values encoded by references, and so the individual rows may eventually be variable in size and I want to be able to maximize the fill level of each page, except possibly the root page). I am finally working on table constructors (to get faster speed, notably for serialization/deserialization of large datasets, for use with common libraries like those handling JSON data).

For tuning parameters, I hope to find a reasonnable strategy that will allow automatic tuning (i.e. based on collecting some runtime statistics and adapt them automatically) without needing any special code in the Lua applications. Extensive tests however are needed in terms of security to avoid changes of tuning parameters to have usable side effects (I will probably add some randomness for threshold conditions where tuning parameters may be changed at runtime; but I still want the system to be reactive and autoadapt itself relatilevely fast, i.e. converge rapidly to a stable solution in about less than one hour).

For the rest, the Lua engine code is almost the same. But it allows Lua to be more safely integrated (including as a library for use in other language environments or in webservers: existing basic Lua is using too much memory, and is too easily attackable, it crashes too often even when using "stable" Lua code and web pages, exhausting maximum time or space quotas, depending on current loads on servers, or depending on server capabilities when using an heterogeneous set of servers with different capabilities: you can already see this bad effect in Wikimedia, notably in WM Commons, even if it still uses an old version of Lua).



Le jeu. 14 oct. 2021 à 11:41, Wendal@合宙 <wendal@openluat.com> a écrit :
it look like "zbuff" , in our "LuatOS" repo.

local buff = zbuff.create(1024)
buff[0] = 0x5A
buff[1] = 0xBA
buff:write(xxxdata) -- no gc ,no malloc at all

https://github.com/openLuat/LuatOS/blob/master/luat/modules/luat_lib_zbuff.c

--------------原始邮件--------------
发件人:"Flyer31 Test "<flyer31@googlemail.com>;
发送时间:2021年10月14日(星期四) 下午5:30
收件人:"Lua mailing list" <lua-l@lists.lua.org>;
主题:Using fixed string buffers to avoid extensive allocs for small strings
-----------------------------------
Hi,
I am currently designing a Lua32 application on a very
memory-restricted system with ca. 256kB ROM and 128kB RAM for some IoT
application.

ROM space is very well sufficient for me for Lua, I need only about 100kB.

But RAM alloc space should be limited to something in the range 30kB,
and this for me somehow seems to be impossible if I allow Lua its
"normal" extensive string allocation, which it does extensively even
for smallest strings. E. g. when I want to re-program my Lua user
program, the complete Lua ASCII program file will split into small
segments of 4-8 bytes, and if I do this with strings (just concat ..
and string.sub), then quite fast the 30kB memory limit will be hit...
. I tried to invoke the garbage collector in regular intervals (I use
yielding, so e. g. after every yield cycle...), then the garbage
collector invocation typically will fail after the 2nd invocation with
the some "memory problem" error message... (my alloc function refuses
any alloc attempt above 50 or 60kB).

So now I wanted to do a cute small library with fixed string buffers,
which I call strbuf. This buffers use a limited buffer size, in case
of any overflow they will mark the string with a final "~" sign, this
should be fine ... . Typically the strings in my programs anyway are
limited to 100 chars / typical line length, but this already would be
extreme ... most strings are much shorter (e. g. "myriads of strings"
with 4-8 chars as described above).

I want to use the following programming style for this in Lua (e. g.
defining two such buffers Tmp and InBuf, and then playing around with
them a bit):

Tmp= strbuf.new(100)
InBuf= strbuf.new( 100)

    Tmp[1]= 'hallo'
    InBuf[1]= Tmp
    InBuf[1]= Tmp[1]


This works all very nicely with a very simple strbuf lib which uses a
metatable and supports __index / __newindex:

    Tmp[1]= 'hallo' invokes __newindex for Tmp and then fills the Tmp-Buffer
    InBuf[1]= Tmp invokes __newindex for InBuf and copies Tmp-Buffer
to InBuf-Buffer
    InBuf[1]= Tmp[1] invokes __index for Tmp, copies to a
(user-hidden) global strbuf element
                                              __STRBUF, and returns
this __STRBUF, then it will inoke
                                              __newindex for InBuf and
gets __STRBUF (it is important here to
                                              use __STRBUF, otherwise
__index of Tmp would have to return a
                                              string, but this then is
again will result in stupid allocs...).

I can extend this quite easily also to further cute applications, e. g.
Tmp[n]= InBuf[m]      (to overwrite char n... of Tmp with char m... of InBuf)
                                  (also negative n/m allowed, then
counting from string end...)
index_of_f = Tmp['f']     to get the index of some substring (e. g. 'f')
1== Tmp['f']                   to check whether Tmp starts with 'f'
Tmp[n]= mul                  to "multiply" the n'th char of Tmp (or
delete if mul negative)

... and later also of course things like Tmp==InBuf, or Tmp[5]==InBuf,
or Tmp..Inbuf, or Tmp[m]..Inbuf[n] ... (or some additional helper
functions like strbuf.format or strbuf.scan...)

... this really looks very cute to me, I am happy with this, and I was
very impressed how fast this could be accomplished with this metatable
functionality of Lua, thank you for this...

Just there is one very dangerous and nerving error source for the user now:

If the user by some accident writes
Tmp='hallo'

instead of
Tmp[1]='hallo'

Because in this case then __newindex will NOT invoke, but instead by
Tmp varialble will somehow "nervingly" will be converted to a
string... .

Do you have some smart idea do avoid this, or block this type
conversion of my nice strbuf variables by Lua error?

Nice would be, that any such strbuf element (generated by strbuf.new,
and thus having this metatable strbuf...) should NOT be allowed to
"change type" any more, orto be re-assigned to anything else (but of
course Tmp[1]=... should still be possible and invoke __index).

Super-great of course would be, if my c software could be notified by
Tmp='hallo' (e. g. if there would be some meta function "__new" or
"__reassign" or so ... but this I did not find unfortunately... I am
quite sure the Lua machine will do this Tmp='hallo' typically extremly
fast without checking any metatables of Tmp?).