Controlling the allocation / deallocation rates when using datatypes

[M88]

Hello,

I just started dabbling with ATS, so bear with me.

I really like using datatypes / datavtypes as a control structure, but the allocation / deallocation rates seem fairly high when there are a fair number created in sequence.  

I suppose I've gotten used to the stream-fusion motif in Haskell.  I'm aware of the caveats of directly translating from one language to another (eg, optimizations like stream-fusion may not hold, nor are they necessary, per se), but I like the idea of the enum-based  state machine.  For example:

datatype Step (s:t@ype, a:t@ype) =
      | Yield of (s,a)
      | Step of (s)
      | Done

When I do something like, say, generate 1000000 of these guys, my allocation / deallocation rates are pretty high, and I suspect it's impacting performance (eg, relative performance with -O2: a stack-only version with unboxed tuple "Step" runs in 11ms, a datavtype version runs in closer to 35ms, getting 44ms-60ms with GC and datatypes, while a naive shot in Haskell runs in 9ms).

I could use something like this, but it is much less elegant (this is how I implemented the stack-only version):

datatype StepType =
    | Yield
    | Skip
    | Done


typedef Step (s:t@ype, a:t@ype) = @(StepType,s,a)

I'm wondering if it's possible to do any of the following (or if ATS might already be doing it for me):

a.) Statically allocate a single variable of a given datatype, and/or create the datatype at a specific memory location

b) Define an initial heap size that stays constant throughout the lifetime of a program, so that transient entities like the ones above consistently re-use the same memory pool.

I think I could probably conjure up something like the latter using custom allocation functions (eg, DATS_MEMALLOC_USER), but I thought I would reach out first...

[gmhwxi]

I suppose I've gotten used to the stream-fusion motif in Haskell.  I'm aware of the caveats of directly translating from one language to another (eg, optimizations like stream-fusion may not hold, nor are they necessary, per se), but I like the idea of the enum-based  state machine.  For example:

It is unclear what you translated. Could you show?

When I do something like, say, generate 1000000 of these guys, my allocation / deallocation rates are pretty high, and I suspect it's impacting performance (eg, relative performance with -O2: a stack-only version with unboxed tuple "Step" runs in 11ms, a datavtype version runs in closer to 35ms, getting 44ms-60ms with GC and datatypes, while a naive shot in Haskell runs in 9ms).

Usually, this means that the ATS code and the Haskell code do things algorithmically different.

a.) Statically allocate a single variable of a given datatype, and/or create the datatype at a specific memory location

b.) Define an initial heap size that stays constant throughout the lifetime of a program, so that transient entities like the ones above consistently re-use the same memory pool.

I believe that the answers to both a) and b) are positive. Here is a link that might be useful:

http://ats-lang.sourceforge.net/EXAMPLE/EFFECTIVATS/linear-streams/main.html#a-linear-stream-based-solution-to-the-eight-queen-puzzle

If you show me some code regarding a), I will be happy show you the way by rewriting it.

[M88]

It is unclear what you translated. Could you show?

I was just saying that I didn't expect the compiler to treat stream-fusion the same way in ATS as it does in Haskell. To your point, I expected different algorithms.

I found the tutorial useful -- implementing a custom allocation routine was easier than I expected it to be. I managed to get the version with datavtypes to run as quickly as the stack version (eg, ~12ms).   I need to refine it a bit more, but that's the start I was looking for.

I would be interested in seeing an implementation of a). I attached the original datavtype version of the code I was using to test.  This is a toy program that creates a stream and prints the final value.

[gmhwxi]

After reading your code, I guess that the following example could be relevant:

http://ats-lang.sourceforge.net/DOCUMENT/INT2PROGINATS/HTML/HTMLTOC/x2223.html

By the way, you could flatten the 'option'-values in your loop:

fun
{s,a:t@ype}
getlast
(
  str : !Stream(s,a)
) : Option_vt(a) =
loop(f_,s_i,0,mx)
    where {
        val mx =
        $UNSAFE.cast{a}(0)
        val Stream(s_i,f_) = str
    fun loop( f  : !s -<cloptr1> Step (s,a),
                  st : s,
                  t0 : int, mx : a )
          : Option_vt(a) =
                case f(st) of
                 | ~Yield(st_,x_) => loop(f,st_, 1, x_)
                 | ~Skip (st_   ) => loop(f,st_, t0, mx)
                 | ~Done (      ) => if t0 > 0 then Some_vt(mx) else None_vt()
      }

I was able to nearly half the execution time by doing the flattening.

There is a safe way to do this. Please see some examples involving opt_none and opt_some.

[gmhwxi]

If efficiency is a big concern, I suggest the coding style shown at:

https://pastebin.com/D8zdEmYH

which minimizes the use of malloc/free.

[M88]

Thank you -- the rewrite was informative, and the most efficient so far.

I overlooked the fact that a datatype is a pointer to an unboxed tuple.  It should make it possible to statically allocate them, if I wanted to.

It looks like there are several options here.