Hi,

I am fairly new to Zig.

And I am aware that most of the help discussion happens on discord
these days - and I am there as well - still I feel more comfortable with old school e-mail.

Thus bear with me please, (and tldr :-( ):

I am attaching a small example program ex.zig below with three functions
f1, f2, f3 (besides main, and some helpers...), which exercise different
types of allocator usage: I am trying to figure out best
practices in this regard.

When I run the program, each of the functions f1, f2, f3 is executed 20
times, and the output (in color) is:

--8<---------------cut here---------------start------------->8---
$ ./ex
(f1 0 bar :dry #t) ...
(f1 1 bar :dry #t) ...
(f1 2 bar :dry #t) ...
(f1 3 bar :dry #t) ...
(f1 4 bar :dry #t) ...
(f1 5 bar :dry #t) ...
(f1 6 bar :dry #t) ...
(f1 7 bar :dry #t) ...
(f1 8 bar :dry #t) ...
(f1 9 bar :dry #t) ...
(f1 10 bar :dry #t) ...
(f1 11 bar :dry #t) ...
(f1 12 bar :dry #t) ...
(f1 13 bar :dry #t) ...
(f1 14 bar :dry #t) ...
(f1 15 bar :dry #t) ...
(f1 16 bar :dry #t) ...
(f1 17 bar :dry #t) ...
(f1 18 bar :dry #t) ...
(f1 19 bar :dry #t) ...
(f2 0 bar :dry #t) ...
(f2 1 bar :dry #t) ...
(f2 2 bar :dry #t) ...
(f2 3 bar :dry #t) ...
(f2 4 bar :dry #t) ...
(f2 5 bar :dry #t) ...
(f2 6 bar :dry #t) ...
(f2 7 bar :dry #t) ...
(f2 8 bar :dry #t) ...
(f2 9 bar :dry #t) ...
(f2 10 bar :dry #t) ...
(f2 11 bar :dry #t) ...
(f2 12 bar :dry #t) ...
(f2 13 bar :dry #t) ...
(f2 14 bar :dry #t) ...
(f2 15 bar :dry #t) ...
(f2 16 bar :dry #t) ...
(f2 17 bar :dry #t) ...
(f2 18 bar :dry #t) ...
(f2 19 bar :dry #t) ...
(f3 0 bar :dry #t) ...
(f3 1 bar :dry #t) ...
(f3 2 bar :dry #t) ...
(f3 3 bar :dry #t) ...
(f3 4 bar :dry #t) ...
(f3 5 bar :dry #t) ...
(f3 6 bar :dry #t) ...
(f3 7 bar :dry #t) ...
(f3 8 bar :dry #t) ...
(f3 9 bar :dry #t) ...
(f3 10 bar :dry #t) ...
(f3 11 bar :dry #t) ...
(f3 12 bar :dry #t) ...
(f3 13 bar :dry #t) ...
(f3 14 bar :dry #t) ...
(f3 15 bar :dry #t) ...
(f3 16 bar :dry #t) ...
(f3 17 bar :dry #t) ...
(f3 18 bar :dry #t) ...
(f3 19 bar :dry #t) ...
--8<---------------cut here---------------end--------------->8---


I have uploaded the program as a github gist as well (not sure if this
works - thus this time included in this very e-mail below as well
- next time maybe as a gh gist only):


--8<---------------cut here---------------start------------->8---
https://gist.github.com/reuleaux/e2e95ad3c3910e9c015738b530ead5b7
--8<---------------cut here---------------end--------------->8---

with output in color (as in my comment to the above gist):

--8<---------------cut here---------------start------------->8---
https://user-images.githubusercontent.com/3234406/204938690-8651a852-cef5-48d4-9618-a50213423c78.png
--8<---------------cut here---------------end--------------->8---


And these functions f1/f2/f3 need some memory:

for coloring a compile time known string like ":dry" in green,
this is not an issue: my helper function green can figure that out at compile
time (and likewise cyan, ...). - Other strings are known at run time only, and thus the
corresponging underscore functions _green, _cyan, _yellow have to
allocate some memory at runtime. - (And I have to allocate memory
in other places, too: std.mem.concat e.g.).


Anyway, now my questions (when running this program):

f1 uses a fixed buffer allocator:
    
--8<---------------cut here---------------start------------->8---
var buffer: [8425]u8 = undefined;
var fba = std.heap.FixedBufferAllocator.init(&buffer);
--8<---------------cut here---------------end--------------->8---


and I have a hard time freeing all the allocated memory in f1:
the 8425 bytes above are just at the limit: if I run f1 21 times,
my program crashes with

--8<---------------cut here---------------start------------->8---
error: OutOfMemory
...
--8<---------------cut here---------------end--------------->8---


Ideally, I should be able to free *all* the memory allocated (for
printing in color etc.) in f1 - each time I run f1 i.e. - and it
shouldn't make a difference if I run f1 20 times or 21 times (or a 1000
times for that matter) - in practice it does make difference: my f1
function leaks memory, and this could be an interesting exercise:
rewrite f1, such that the 8425 bytes fixed buffer allocator above is
large enough to run f1 a 1000 times (I am not sure if this is possible
at all).

I have tried to free some memory in f1, for example: I write
    
--8<---------------cut here---------------start------------->8---
var xs_str = try std.mem.concat (args.allocator.*, u8, xs.items);
defer args.allocator.*.free(xs_str);
std.debug.print("{s}\n", .{ xs_str });
--8<---------------cut here---------------end--------------->8---

instead of originally just:

--8<---------------cut here---------------start------------->8---
std.debug.print("{s}\n", .{ try std.mem.concat (args.allocator.*, u8, xs.items)});
--8<---------------cut here---------------end--------------->8---

at the end, otherwise, it would crash with OutOfMemory, even when
running f1 just 20 times.

Apparently these efforts of mine to free memory were not aggressive
enough (there are some more attempts of mine in the comments - which
apparently don't make a difference), like writing:

                

--8<---------------cut here---------------start------------->8---
// var dry_str: []const u8 = undefined;
// defer args.allocator.*.free(dry_str);

// if (args.dry orelse false) {
//     dry_str = try frmt.allocPrint(args.allocator.*, "{s} {s}", .{green(":dry"), yellow ("#t")} );
//     try as.append(dry_str);
// }
--8<---------------cut here---------------end--------------->8---

instead of just

--8<---------------cut here---------------start------------->8---
if (args.dry orelse false) {
    try as.append(try frmt.allocPrint(args.allocator.*, "{s} {s}", .{green(":dry"), yellow ("#t")} ));
}
--8<---------------cut here---------------end--------------->8---



Anyway, this is kind of a tedious exercise. - And I have since learned to
appreciate the arena allocator: f2 and f3 both practice the arena
allocator.

Now f2 is the analogue to f1: prepare the allocator in main,
        
--8<---------------cut here---------------start------------->8---
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
--8<---------------cut here---------------end--------------->8---


and pass it to function f2: this works, but is not really what I want:
a huge amount of memory is allocated by running f2 20 times, and
only at the very end (of main) this memory is freed.

I would rather want to allocate and free small chunks of memory often -
and this is what I am trying to achieve in function f3 - such that
it doesn't make a difference (in terms of memory usage), if I run
f3 20 times or a 1000 times: clean up after each run of f3.

Thus my function f3 does not take an allocator parameter, but
initialises (and frees) its own allocator:

--8<---------------cut here---------------start------------->8---
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
var allocator = arena.allocator();
--8<---------------cut here---------------end--------------->8---
    
Now, I am not sure: is this the right way to do it? - Isn't this
way too much administrative overhead?

Also, I am surprised: I would have thought, the arena allocator
is used differently:

initialise it once (in main) - i.e. do all the (possibly costly) administrative stuff just
once - and then use it (reuse it multiple times in f3): i.e. pass it f3,
use it there, and free it (deinit it) repeatedly. - But apparently this is
not how it works: 

if I init it in main

--8<---------------cut here---------------start------------->8---
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
--8<---------------cut here---------------end--------------->8---

pass it to f3, and then deinit it in f3

--8<---------------cut here---------------start------------->8---
defer arena.deinit();
--8<---------------cut here---------------end--------------->8---

my program crashes:

Thus to summarise: what are best practices for using the arena
allocator in a "allocate and free small chunks of memory often" fashion?

Thanks,
  -A




ex.zig

--8<---------------cut here---------------start------------->8---
const std = @import("std");
const os = std.os;


const ArrayList = std.ArrayList;

const Allocator = std.mem.Allocator;
const frmt = std.fmt;





fn f1(args: struct {allocator: *Allocator,
                    number: ?i32 = null,
                    foo: ?[]const u8 = null,
                    dry: ?bool = null,}) !void {
    
    
    var as = std.ArrayList([]const u8).init(args.allocator.*);
    defer as.deinit();

    var xs = std.ArrayList([]const u8).init(args.allocator.*);
    defer xs.deinit();

    
    try as.append("f1");

    
    // this one in yellow
    
    if (args.number) |n| {
        try as.append(try _yellow(args.allocator, try frmt.allocPrint(args.allocator.*, "{d}", .{n})));
    }
    


    // var num_str: []const u8 = undefined;
    // defer args.allocator.*.free(num_str);

    // if (args.number) |n| {
    //     num_str = try _yellow(args.allocator, try frmt.allocPrint(args.allocator.*, "{d}", .{n}));
    //     try as.append(num_str);
    // }
    
    
    
    if (args.foo) |foo| {
        try as.append(foo);
    }


                
    if (args.dry orelse false) {
        try as.append(try frmt.allocPrint(args.allocator.*, "{s} {s}", .{green(":dry"), yellow ("#t")} ));
    }

    // var dry_str: []const u8 = undefined;
    // defer args.allocator.*.free(dry_str);
    
    // if (args.dry orelse false) {
    //     dry_str = try frmt.allocPrint(args.allocator.*, "{s} {s}", .{green(":dry"), yellow ("#t")} );
    //     try as.append(dry_str);
    // }

    
    
    
    // separated by space, and in cyan

    try xs.append("(");
    try xs.append (try _cyan (args.allocator, as.items[0]));
    
    for (as.items[1..]) |el| {
        try xs.append (" ");
        try xs.append (try _cyan (args.allocator, el));
    }
    
    try xs.append(")");
    try xs.append (" ...");

    
    // std.debug.print("{s}\n", .{ try std.mem.concat (args.allocator.*, u8, xs.items)});
    
    var xs_str = try std.mem.concat (args.allocator.*, u8, xs.items);
    defer args.allocator.*.free(xs_str);
    std.debug.print("{s}\n", .{ xs_str });
    
}







fn f2(args: struct {
    arena: *std.heap.ArenaAllocator,
    number: ?i32 = null,
    foo: ?[]const u8 = null,
    dry: ?bool = null }) !void {
    

    
    // var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    // defer arena.deinit();
    var allocator = args.arena.*.allocator();
    

    var as = std.ArrayList([]const u8).init(allocator);
    defer as.deinit();

    var xs = std.ArrayList([]const u8).init(allocator);
    defer as.deinit();

    
    try as.append("f2");

    
    // this one in yellow
    if (args.number) |n| {
        try as.append(try _yellow(&allocator, try frmt.allocPrint(allocator, "{d}", .{n})));
    }

    if (args.foo) |foo| {
        try as.append(foo);
    }

    
    
    if (args.dry orelse false) {
        try as.append(try frmt.allocPrint(allocator, "{s} {s}", .{green(":dry"), yellow ("#t")} ));
    }


    try xs.append ("(");
    try xs.append(as.items[0]);
    
    for (as.items[1..]) |el| {
        try xs.append (" ");
        try xs.append (try _cyan (&allocator, el));
    }
    try xs.append(") ...");
    
    std.debug.print("{s}\n", .{ try std.mem.concat (allocator, u8, xs.items)});

    
}


fn f3(args: struct {
    // arena: *std.heap.ArenaAllocator,
    number: ?i32 = null,
    foo: ?[]const u8 = null,
    dry: ?bool = null }) !void {
    

    
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    var allocator = arena.allocator();
    

    var as = std.ArrayList([]const u8).init(allocator);
    defer as.deinit();

    var xs = std.ArrayList([]const u8).init(allocator);
    defer as.deinit();

    
    try as.append("f3");

    
    // this one in yellow
    if (args.number) |n| {
        try as.append(try _yellow(&allocator, try frmt.allocPrint(allocator, "{d}", .{n})));
    }


    if (args.foo) |foo| {
        try as.append(foo);
    }


    
    
    if (args.dry orelse false) {
        try as.append(try frmt.allocPrint(allocator, "{s} {s}", .{green(":dry"), yellow ("#t")} ));
    }


    try xs.append ("(");
    try xs.append(as.items[0]);
    
    for (as.items[1..]) |el| {
        try xs.append (" ");
        try xs.append (try _cyan (&allocator, el));
    }
    try xs.append(")");
    try xs.append (" ...");
    
    std.debug.print("{s}\n", .{ try std.mem.concat (allocator, u8, xs.items)});

    
}







const cyan_ = "\x1b[0;36m";
const yellow_ = "\x1b[0;33m";
const green_ = "\x1b[0;32m";
const reset_ = "\x1b[0m";

// comptime s
fn cyan(comptime s: []const u8) []const u8 {
    return cyan_ ++ s ++ reset_; 
}

// runtime s
fn _cyan(alloc: *Allocator, s: []const u8) ![]const u8 {
    return std.mem.concat( alloc.*, u8, &[_][]const u8{ cyan_, s, reset_ } );
    // return std.mem.concat( alloc.*, u8, .{ cyan_, s, reset_ } ); 
}


fn green(comptime s: []const u8) []const u8 {
    return green_ ++ s ++ reset_; 
}

fn yellow(comptime s: []const u8) []const u8 {
    return yellow_ ++ s ++ reset_; 
}

fn _yellow(alloc: *Allocator, s: []const u8) ![]const u8 {
    return std.mem.concat( alloc.*, u8, &[_][]const u8{ yellow_, s, reset_ } );
    // return std.mem.concat( alloc.*, u8, .{ yellow_, s, reset_ } ); 
}




// from https://github.com/nektro/zig-range/blob/master/src/lib.zig
pub fn range(len: usize) []const void {
    return @as([*]void, undefined)[0..len];
}



pub fn main() !void {



    // // const hp_alloc = std.heap.page_allocator;
    // var hp_alloc = std.heap.page_allocator;
    // // _ = hp_alloc; 

    
    var buffer: [8425]u8 = undefined;
    var fba = std.heap.FixedBufferAllocator.init(&buffer);

    var fb_alloc = fba.allocator();
    // _ = fb_alloc; 

    
    
    // var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    // defer _ = gpa.deinit();
    // const gp_alloc = gpa.allocator();
    // var gp_alloc = gpa.allocator();



    

    for (range(20)) |_,i| {
        try f1( .{ .allocator=&fb_alloc
                      , .number = @intCast(i32, i)
                      , .foo = "bar"
                      , .dry = true
                  });
    }
    
        
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    
    
    for (range(20)) |_,i| {
        try f2( .{
            .arena=&arena
                , .number = @intCast(i32, i)
                , .foo = "bar"
                , .dry = true
                
        });
    }


    
    for (range(20)) |_,i| {
        try f3( .{
            .number = @intCast(i32, i)
                , .foo = "bar"
                , .dry = true
                
        });
    }

    
    
    
}






--8<---------------cut here---------------end--------------->8---

On 11/30/22 19:51, Andreas Reuleaux wrote:
> And I am aware that most of the help discussion happens on discord
> these days - and I am there as well - still I feel more comfortable with old school e-mail.
 > ...

I agree that email is more convenient than forums, so I'm happy to see 
your traffic. I didn't look at your code, but I think the arena 
allocator has a free procedure which will do the trick. Take a look at 
zig/lib/std/heap/arena_allocator.zig

-- 
Anthony Carrico

OK, I will have a look. - Thanks (so far).

-A


Anthony Carrico <acarrico@memebeam.org> writes:

> On 11/30/22 19:51, Andreas Reuleaux wrote:
>> And I am aware that most of the help discussion happens on discord
>> these days - and I am there as well - still I feel more comfortable
>> with old school e-mail.
>> ...
>
> I agree that email is more convenient than forums, so I'm happy to see
> your traffic. I didn't look at your code, but I think the arena 
> allocator has a free procedure which will do the trick. Take a look at
> zig/lib/std/heap/arena_allocator.zig

Anthony Carrico <acarrico@memebeam.org> writes:

> On 11/30/22 19:51, Andreas Reuleaux wrote:
>> And I am aware that most of the help discussion happens on discord
>> these days - and I am there as well - still I feel more comfortable with old school e-mail.
>> ...
>
> I agree that email is more convenient than forums, so I'm happy to see
> your traffic. I didn't look at your code, but I think the arena 
> allocator has a free procedure which will do the trick. Take a look at
> zig/lib/std/heap/arena_allocator.zig

To come back to my earlier question (having looked at
zig/lib/std/heap/arena_allocator.zig):

There is indeed a free procedure in
zig/lib/std/heap/arena_allocator.zig, but it is not public
(and thus not meant to be used).


The documentation at
https://ziglang.org/documentation/master/std/#root;heap.ArenaAllocator
(and all the examples I have seen) suggests the use of just these three
functions (as I have done):

  fn allocator(self: *ArenaAllocator) Allocator
  fn deinit(self: ArenaAllocator) void
  fn init(child_allocator: Allocator) ArenaAllocator

It is (still) not clear to me, how costly these init/deinit operations are,
and if calling them with every call of f3 in my example (and thus 20
times) is too costly perhaps [?].

As the arena allocator takes another allocator as an argument: maybe
initialising it with memory from the stack is less expensive (and the way
to proceed thus in my example [?] - assuming that memory from the stack
is faster than from the heap. - But I haven't seen any such example
usage.

A further discussion, about how costly the arena allocator is,
and some best practices for its usage, would be very much appreciated.

Thanks again,
 -A

On Mon, Dec 5, 2022 at 3:33 AM Andreas Reuleaux <rx@a-rx.info> wrote:
>
> Anthony Carrico <acarrico@memebeam.org> writes:
>
> It is (still) not clear to me, how costly these init/deinit operations are,
> and if calling them with every call of f3 in my example (and thus 20
> times) is too costly perhaps [?].

I'm also a newbie to zig, but I'll attempt to answer your questions
because I've been digging into the allocator interface myself. If I
understand your requirement correctly, what you need to do is
instantiate an ArenaAllocator inside f1, f2 and f3 and pass the
args.allocator.* as the backing allocator. Use this allocator to
allocate all memory within the function.

And yes, ArenaAllocator init and deinit will happen every time you
call the function (20 times for twenty calls) but this is okay since
the ArenaAllocator will consolidate multiple allocs and will call the
backing store free fewer times.

It's very interesting and illuminating to use the logging allocator to
see how the allocs and frees happen. In your main function, try:

===
    -var fb_alloc = la.allocator();
    +var la = std.heap.loggingAllocator(fba.allocator());
    +var fb_alloc = la.allocator();
===

When you use an ArenaAllocator inside f1 on top of this change, you'll
see that the arena allocator will keep resizing as you make
allocations and will eventually do a single free. A good optimization
for the arena_allocator is to grow exponentially (like an ArrayList)
rather than resizing every alloc.

Ganesan

-- 
Ganesan Rajagopal

Hi, and thanks for answering / getting back to me.

Ganesan Rajagopal <rganesan@gmail.com> writes:

> On Mon, Dec 5, 2022 at 3:33 AM Andreas Reuleaux <rx@a-rx.info> wrote:
>>
>> Anthony Carrico <acarrico@memebeam.org> writes:
>>
>> It is (still) not clear to me, how costly these init/deinit operations are,
>> and if calling them with every call of f3 in my example (and thus 20
>> times) is too costly perhaps [?].
>
> I'm also a newbie to zig, but I'll attempt to answer your questions
> because I've been digging into the allocator interface myself. If I
> understand your requirement correctly, what you need to do is
> instantiate an ArenaAllocator inside f1, f2 and f3 and pass the
> args.allocator.* as the backing allocator. Use this allocator to
> allocate all memory within the function.

We are really only talking about (the twenty calls of) f3 here. -
f1 and f2 I merely used to show, how *not* to work with allocators.

>
> And yes, ArenaAllocator init and deinit will happen every time you
> call the function (20 times for twenty calls) but this is okay since
> the ArenaAllocator will consolidate multiple allocs and will call the
> backing store free fewer times.


So I understand, that the way I use the arena allocator at the beginning of
f3 is indeed the correct way to do it:

   fn f3(...) {

       var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
       defer arena.deinit();
       var allocator = arena.allocator();

       ...
       <use allocator within f3>
       ...
}

But now I am wondering, if this is also the cheapest way to do it: maybe rather
than initialising it completely from scratch: with
std.heap.page_allocator, use some (already prepared) underlying
allocator paramter, like so:



   fn f3(..., underlying_allocator_param, ...) {

       var arena = std.heap.ArenaAllocator.init(underlying_allocator_param);
       defer arena.deinit();
       var allocator = arena.allocator();

       ...
       <use allocator within f3>
       ...
}


and make sure, this (potentially costly) prepartion of
underlying_allocator_param is done only once in main?

I will keep digging deeper, continue to experiment.


>
> It's very interesting and illuminating to use the logging allocator to
> see how the allocs and frees happen. In your main function, try:
>
> ===
>     -var fb_alloc = la.allocator();
>     +var la = std.heap.loggingAllocator(fba.allocator());
>     +var fb_alloc = la.allocator();
> ===
>
> When you use an ArenaAllocator inside f1 on top of this change, you'll
> see that the arena allocator will keep resizing as you make
> allocations and will eventually do a single free. A good optimization
> for the arena_allocator is to grow exponentially (like an ArrayList)
> rather than resizing every alloc.
>
> Ganesan

And yes, thanks for this logging allocator hint: I will try this as well.

-A

> We are really only talking about (the twenty calls of) f3 here. -
> f1 and f2 I merely used to show, how *not* to work with allocators.

Ah, got it.

> So I understand, that the way I use the arena allocator at the beginning of
> f3 is indeed the correct way to do it:
>
>    fn f3(...) {
>
>        var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
>        defer arena.deinit();
>        var allocator = arena.allocator();
>
>        ...
>        <use allocator within f3>
>        ...
> }
>
> But now I am wondering, if this is also the cheapest way to do it: maybe rather
> than initialising it completely from scratch: with
> std.heap.page_allocator, use some (already prepared) underlying
> allocator paramter, like so:

Right. You can pass in the FixedBufferAllocator as the backing
allocator as you're already doing for f1. That should be quite cheap.
Your example code runs for me with a small fixed buffer of 1K as the
backing allocator for the arena allocator.

Ganesan