How strict is Lua in honoring collectgarbage() and its subcommands?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

How strict is Lua in honoring collectgarbage() and its subcommands?

Brigham Toskin
Hey all.

I've been prototyping several different implementations of lisp-style linked lists. To get an idea of their performance characteristics, I wrote a series of braindead but probably indicative micro benchmarks.

Now, because I'm trying to get a feel for how the manipulations themselves perform in isolation, I am passing "stop" to collectgarbage() between tests, collecting my data, then using the "restart" command and running two full passes of the gc to clean up before the next test.

The data collection consists of using the "count" subcommand and os.clock to get memory usage wall time before the test, running the micro benchmark, and then checking the difference. The memory usage numbers seem incredibly high (like 40 MB of memory gets allocated when I load up 2 KB (256 * sizeof(double)) of numbers and iterate over them).

Turning the gc off at the start and leaving it off the whole time doesn't seem to make any difference in timing or memory per test. What *does* make a huge difference though is the order I run the tests in. If I use a pair list (where l[1] is the value and l[2] is the next pair node) after two other implementations, it is an order of magnitude slower us uses a lot more memory.

Obviously os.clock has limitations–which I'm okay with, since I don't need exact profiling data–but how accurate is collectgarbage("count")? The manual says it returns usage in "K bytes", so to get the answer in megs I divide by 1024; is this a reasonable adjustment for what it's actually returning? Does Lua actually respect the "stop" subcommand? Is the perhaps an issue more of the allocator than the garbage collector? I could be leaking memory, but 40 MB seems excessive.

Thoughts? Am I approaching my measurements completely wrong?

--
Brigham Toskin
Reply | Threaded
Open this post in threaded view
|

Re: How strict is Lua in honoring collectgarbage() and its subcommands?

Tim Hill

> On May 28, 2015, at 1:01 PM, Brigham Toskin <[hidden email]> wrote:
>
> Hey all.
>
> I've been prototyping several different implementations of lisp-style linked lists. To get an idea of their performance characteristics, I wrote a series of braindead but probably indicative micro benchmarks.
>
> Now, because I'm trying to get a feel for how the manipulations themselves perform in isolation, I am passing "stop" to collectgarbage() between tests, collecting my data, then using the "restart" command and running two full passes of the gc to clean up before the next test.
>
>
> Thoughts? Am I approaching my measurements completely wrong?
>
> --
> Brigham Toskin

Can you post sample code?

—Tim


Reply | Threaded
Open this post in threaded view
|

Re: How strict is Lua in honoring collectgarbage() and its subcommands?

Brigham Toskin
https://github.com/IonoclastBrigham/firth/blob/bootstrap/proto/listproto.lua

It's a bit of a mess, as one might expect from prototype code, but I can't even really do much to clean it up because I don't really understand what going on.

The first two versions, labeled "Hash-Linked" and "Index-Linked" were ideas that popped into my head at like 4 in the morning. They seem somewhat impractical overall (and most definitely leak memory), but I was curious if potential cache benefits might make pursuing one or both worth while. "Traditional" is a lisp-style linked list based on pairs where the second element is the next node table. And "Array-Tables" is just list-style manipulators wrapped around a lua array table for reference.

Of particular note, "Traditional" claims to use less memory and run faster if it comes before the others. Scratching my head on that one. Heap fragmentation? Rogue collector disobeying my commands? Did I cross the particle streams somewhere and open a portal to Gozer?

On Thu, May 28, 2015 at 5:19 PM, Tim Hill <[hidden email]> wrote:

> On May 28, 2015, at 1:01 PM, Brigham Toskin <[hidden email]> wrote:
>
> Hey all.
>
> I've been prototyping several different implementations of lisp-style linked lists. To get an idea of their performance characteristics, I wrote a series of braindead but probably indicative micro benchmarks.
>
> Now, because I'm trying to get a feel for how the manipulations themselves perform in isolation, I am passing "stop" to collectgarbage() between tests, collecting my data, then using the "restart" command and running two full passes of the gc to clean up before the next test.
>
>
> Thoughts? Am I approaching my measurements completely wrong?
>
> --
> Brigham Toskin

Can you post sample code?

—Tim





--
Brigham Toskin
Reply | Threaded
Open this post in threaded view
|

Re: How strict is Lua in honoring collectgarbage() and its subcommands?

Philipp Janda
In reply to this post by Brigham Toskin
Am 28.05.2015 um 22:01 schröbte Brigham Toskin:
> Hey all.

Hi!

>
> [...]
>
> Obviously os.clock has limitations–which I'm okay with, since I don't need
> exact profiling data–but how accurate is collectgarbage("count")? The
> manual says it returns usage in "K bytes", so to get the answer in megs I
> divide by 1024; is this a reasonable adjustment for what it's actually
> returning? Does Lua actually respect the "stop" subcommand? Is the perhaps
> an issue more of the allocator than the garbage collector? I could be
> leaking memory, but 40 MB seems excessive.

I get about 140 MB in the "Hash-linked" `foreach_sum8` test on a 64-bit
machine.

>
> Thoughts? Am I approaching my measurements completely wrong?
>

For one, you are not measuring what you think you are measuring: The 140
MB is the memory used by 800000 closures with 3 unique upvalues each,
created by the `lvalues()` function. (That's why the `foreach_sum8` test
takes two times more memory than the `foreach_sum4` test, and 8 times
more memory than the `foreach_sum1` tests.) The list elements are just
noise in comparison ...

Philipp



Reply | Threaded
Open this post in threaded view
|

Re: How strict is Lua in honoring collectgarbage() and its subcommands?

Brigham Toskin
On Fri, May 29, 2015 at 3:16 AM, Philipp Janda <[hidden email]> wrote:
I get about 140 MB in the "Hash-linked" `foreach_sum8` test on a 64-bit machine.


Thoughts? Am I approaching my measurements completely wrong?


For one, you are not measuring what you think you are measuring: The 140 MB is the memory used by 800000 closures with 3 unique upvalues each, created by the `lvalues()` function. (That's why the `foreach_sum8` test takes two times more memory than the `foreach_sum4` test, and 8 times more memory than the `foreach_sum1` tests.) The list elements are just noise in comparison ...

Wow, you are so very right. When I was writing this code, I knew there would be a penalty for closures with upvalues, but I figured, "Hey, they're pretty cheap... For a quick and dirty prototype this is probably fine!" But when you multiply "not very much" by 800,000, things start to add up quickly. I didn't actually do the math.

In my latest version,[1] I replaced lvalues() with eachcar(), which returns an iterator (an external local this time, instead of a generated closure). For the traditional pair-list, this returns the cdr (everything after the head, for non-lisp people) and the head value each iteration. This means I can use the list itself as the iteration variable with the generic for mechanism. This is closer to the analog of ipairs(), and runs WAY faster, with a tiny fraction of the memory. And in fact, for "Array-Tables" this actually just calls ipairs() for you.

I'm still seeing the issue where "Traditional" create10()  runs twice as fast and uses about 10% less memory if I comment out the other two tests before it. I'm thinking this has got to do with heap fragmentation, but I try to force the GC to clean that mess up between runs. Even if I set the backing store L to nil and run the GC a couple times, the results are the same.




--
Brigham Toskin