Recent

Author Topic: Enumerator with destructor  (Read 6755 times)

BeniBela

  • Hero Member
  • *****
  • Posts: 905
    • homepage
Enumerator with destructor
« on: June 26, 2016, 02:13:58 pm »
For most lists it is easy to create an enumerator, but lately I was thinking, it would be nice to have an enumerator for a lazy list that calculates the values while enumerating.

This leads to the problem, after the value has been calculated and the enumerator is done, how can you free that value?

I do not want to have the enumerator on the heap, because that is unnecessary slow, so it cannot be a class-based enumerator with destructor.

The record-based enumerator does not have a destructor, so it cannot free the value.

You cannot put a guard interface in the record, because that is even slower.

You cannot free it on movenext returning false, because the loop might be broken.

You cannot precalculate all the values, when the enumerator is created, because that would not be lazily and there would be no point in  this anymore.

You cannot store the currently calculated value in the list, because that is not thread-safe, and also, because you won't know when the enumerator is done.

You cannot keep the enumerator in the lazy list and return an instance of it, because that is not thread safe, either, and you cannot have nested enumerators



So how could it be done?

Ondrej Pokorny

  • Full Member
  • ***
  • Posts: 220
Re: Enumerator with destructor
« Reply #1 on: June 26, 2016, 03:08:40 pm »
I do not want to have the enumerator on the heap, because that is unnecessary slow

The one enumerator object doesn't make a difference if you use a list anyway. Creating one object isn't so slow to manifest the difference.

So how could it be done?

If you want to use a record anyway, use an array instead of list.

guest58172

  • Guest
Re: Enumerator with destructor
« Reply #2 on: June 26, 2016, 03:33:36 pm »
If you make a record-based enumerator, that is probably because you want it to reside on the stack, so you won't allocate it with new. Considering this fact you'll always know when it goes out of scope (e.g as a local variable you know it's dead on return) as a class member you know that it's dead in destroy, etc). So you can add a special procedure that's anyway not used by for..in and call it when you know it's dead.

But it wouldn't be a bad idea to have record destructors that would be automatically called when a record goes out of scope. Languages exist that define this mechanism.  ;)

BeniBela

  • Hero Member
  • *****
  • Posts: 905
    • homepage
Re: Enumerator with destructor
« Reply #3 on: June 26, 2016, 07:51:47 pm »

The one enumerator object doesn't make a difference if you use a list anyway. Creating one object isn't so slow to manifest the difference.


Like 100 ms for 1 million enumerator creations

I was replacing all my for loops with for..in loops. There it sums up

Quote from: ondrejpokorny link=topic=33142.msg214149#msg214149
If you want to use a record anyway, use an array instead of list.

A lazy array?


If you make a record-based enumerator, that is probably because you want it to reside on the stack, so you won't allocate it with new. Considering this fact you'll always know when it goes out of scope (e.g as a local variable you know it's dead on return) as a class member you know that it's dead in destroy, etc). So you can add a special procedure that's anyway not used by for..in and call it when you know it's dead.

Does not seem to work well with for..in loops

There you do not even have the enumerator in a variable



But it wouldn't be a bad idea to have record destructors that would be automatically called when a record goes out of scope. Languages exist that define this mechanism.  ;)

yes!

Although it would be sufficient if it would just do it on enumerators for now

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Enumerator with destructor
« Reply #4 on: June 26, 2016, 09:26:47 pm »
Or simply avoid dynamic data allocation. Use pointers into existing structures and for the rest static or automated types.

Why do you need an destructor anyway if you don't do dynamic memory allocations?

BeniBela

  • Hero Member
  • *****
  • Posts: 905
    • homepage
Re: Enumerator with destructor
« Reply #5 on: June 26, 2016, 09:56:41 pm »
Why do you need an destructor anyway if you don't do dynamic memory allocations?

To make a lazy list

Sometimes you need a lazy list.

For example, you could make an  list of all fibonacci numbers (in a big int class) and then while you enumerate it, the numbers are calculated, till you abort the loop. You could not precalculated them, since it is infinite.

Now the trick is to keep the entire logic in the list, not in the enumerator.  The enumerator should have no idea, what kind of list it enumerates.

A block wise iterator might help with the first steps. It gets a start and end pointer of a block, and a callback function. First it  enumerates everything in the block, which is fast for finite lists (being fast for normal lists is the prime objective, other kinds of list are rare). Then the block is exhausted, and it calls the callback function to get the next block. There would be no limit to the number of blocks


Ondrej Pokorny

  • Full Member
  • ***
  • Posts: 220
Re: Enumerator with destructor
« Reply #6 on: June 26, 2016, 11:11:32 pm »
The one enumerator object doesn't make a difference if you use a list anyway. Creating one object isn't so slow to manifest the difference.
Like 100 ms for 1 million enumerator creations

How long does one whole for-in loop take?

Ondrej Pokorny

  • Full Member
  • ***
  • Posts: 220
Re: Enumerator with destructor
« Reply #7 on: June 26, 2016, 11:13:35 pm »
Btw. for what do you need a lazy list in an enumerator? Enumerators shouldn't need it at all. For the iteration you use Current and MoveNext. No need to have a list at all.

BeniBela

  • Hero Member
  • *****
  • Posts: 905
    • homepage
Re: Enumerator with destructor
« Reply #8 on: June 27, 2016, 04:01:09 pm »
The one enumerator object doesn't make a difference if you use a list anyway. Creating one object isn't so slow to manifest the difference.
Like 100 ms for 1 million enumerator creations

How long does one whole for-in loop take?

Around 500 ms

Each list had  100 integers

Btw. for what do you need a lazy list in an enumerator? Enumerators shouldn't need it at all. For the iteration you use Current and MoveNext. No need to have a list at all.

The list is just the thing that has a GetEnumerator function

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Enumerator with destructor
« Reply #9 on: June 27, 2016, 08:44:26 pm »
Around 500 ms
Each list had  100 integers
That would be either very slow hardware or incompetence.

I get similar results as the 1,000.000 in about 100Msec. I suspect incompetence again.
Can you - for real - produce a simple example that compiles and reproduces the issue?
Specialize a type, not a var.

BeniBela

  • Hero Member
  • *****
  • Posts: 905
    • homepage
Re: Enumerator with destructor
« Reply #10 on: June 27, 2016, 09:36:47 pm »
I get similar results as the 1,000.000 in about 100Msec. I suspect incompetence again.
Can you - for real - produce a simple example that compiles and reproduces the issue?

Code: [Select]
program Project1;

{$mode objfpc}{$H+}

{$modeswitch advancedrecords}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes       //,bbdebugtools
;

{$define ctest}

type tittest = {$ifdef ctest}class{$else}record{$endif}
  a: integer;
  function movenext: boolean;
  property current: integer read a;
  function getEnumerator: tittest;
 {$ifdef ctest2} procedure FreeInstance; override; {$endif}
end;

function tittest.movenext: boolean;
begin
  result := a < 100;
  inc(a);
end;

function tittest.getEnumerator: tittest;
begin
  result := self;
end;
{$ifdef ctest2}
procedure tittest.FreeInstance;
begin

end;
{$endif}

var static: tittest;

type tcaller = record
  function getEnumerator: tittest;
end;
function tcaller.getEnumerator: tittest;
begin
  {$ifdef ctest} result := tittest.Create;{$endif}
  {$ifdef ctest2} result := static;{$endif}
  result.a:=7;
end;

var c: tcaller;
  x, sum, rep, rep2:integer;
begin
  static := tittest.Create;
  logging:=true;
  //for rep2 := 1 to 3 do begin
//  startTiming();
  for rep := 1 to 1000000 do
  for x in c do sum += x;
 // stopTiming();
 // end;
end.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Enumerator with destructor
« Reply #11 on: June 27, 2016, 09:57:56 pm »
Why do you need an destructor anyway if you don't do dynamic memory allocations?

To make a lazy list

Sometimes you need a lazy list.

For..in enumerators are lazy lists. They only have a current and next operation, no count to relay up front. You can make the enumerator a record, and store state in there (e.g. pointers to the real collection).

Quote
For example, you could make an  list of all fibonacci numbers (in a big int class) and then while you enumerate it, the numbers are calculated, till you abort the loop. You could not precalculated them, since it is infinite.

Yes, but for in calculators can't be parameterized during the for loop, so you can't convey when to stop, so that is pointless.


Quote
Now the trick is to keep the entire logic in the list, not in the enumerator.  The enumerator should have no idea, what kind of list it enumerates.

Why? That state is part of the enumeration, not the base list. IMHO an action on an enumerator should NEVER lead to a state change in the base class.

Anyway, I attach an own made list class (replacement for sorted tstringlists for some special cases) that implements iterators for values and keys and for tpairs.

The added demo shows the usage of the value and key iterators. Compile with -ghl and see it is memory safe. There is no iterator state part of the base class. (but the iterator implicitely assumes that
the base class doesn't mutate during iteration, iow is read-only)
 

BeniBela

  • Hero Member
  • *****
  • Posts: 905
    • homepage
Re: Enumerator with destructor
« Reply #12 on: June 27, 2016, 11:45:33 pm »

For..in enumerators are lazy lists. They only have a current and next operation, no count to relay up front. You can make the enumerator a record, and store state in there (e.g. pointers to the real collection).

But not if there is no real collection and the state is calculated during iterating


Yes, but for in calculators can't be parameterized during the for loop, so you can't convey when to stop, so that is pointless.

You can call break to abort it



Why? That state is part of the enumeration, not the base list. IMHO an action on an enumerator should NEVER lead to a state change in the base class.

Because it is fun.



And I might find a use for  it in my interpreter.
It evaluates a user defined program, and the user can create lists and do something with them.
E.g. "1 to 1000000" would create a large list and "subsequence(list(),1,100)" would get the first 100 elements.

Now it is a waste of time to   create the whole list, if both occurs together. The easiest solution is a lazy list. Since the interpreter does not know there will be a subsequence when creating the list, nor does it know how the list was created when subsequence is called

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Enumerator with destructor
« Reply #13 on: June 28, 2016, 09:20:57 pm »
But not if there is no real collection and the state is calculated during iterating

So then you need no baseclass? Then implement everything in the iterator record.


Yes, but for in calculators can't be parameterized during the for loop, so you can't convey when to stop, so that is pointless.

You can call break to abort it
[/quote]

That is still not state information added to the iterator.

Quote

Why? That state is part of the enumeration, not the base list. IMHO an action on an enumerator should NEVER lead to a state change in the base class.

Because it is fun.

Go start make a new language for fun then O:-)

Quote
And I might find a use for  it in my interpreter.
It evaluates a user defined program, and the user can create lists and do something with them.
E.g. "1 to 1000000" would create a large list and "subsequence(list(),1,100)" would get the first 100 elements.

Maybe you are better suited with a functional interpreted language as host for such language, if you want to try to pass functional concepts like that 1:1.


 

TinyPortal © 2005-2018