Jump to content
TurboMagic

Generic circular buffer library released

Recommended Posts

25 minutes ago, Stefan Glienke said:

I admit - it's not common but good luck storing something like this in your list then:

I have no experience with weak refs. Could you describe possible issues?

Share this post


Link to post
1 hour ago, Fr0sT.Brutal said:

I have no experience with weak refs. Could you describe possible issues?

Simple: pointers stored in the weakref table in System don't match those after using Move

Share this post


Link to post
3 hours ago, Stefan Glienke said:

Leave implementing generic collections to people experienced with it

...and how did these people get their experience? :classic_wink:

Share this post


Link to post
57 minutes ago, Anders Melander said:

...and how did these people get their experience? :classic_wink:

Keep in mind this was addressed at Uwes comment that he did not publish something similar because he did not make the effort to make it work not only for his but as a general purpose thing.

 

I cannot speak for others but for me it was reading a lof of collection library code (not only Delphi) - the Delphi specific things (can/cannot use System.Move and such) comes from general core runtime (RTL) knowledge.

And sometimes after years it dawns on you that naive usage of generics in large OOP architectures is not the greatest thing and you start refactoring stuff.

Edited by Stefan Glienke
  • Like 4

Share this post


Link to post
On 8/23/2020 at 4:31 PM, TurboMagic said:

Uwe Raabe is already working on this 😉

But others than MVPs and the usual folks could contribiute as well...

Often such easy things or even parts of those would help the community!

Since I didn't hear from him with a ull request or any other "delivery" yet I guess he got stuck translating the comments...

Share this post


Link to post
9 hours ago, Anders Melander said:

I can't see why using Move would be a problem as long as it just moves entries within the buffer array (which it does as far as I can tell).

However there does seem to be a problem with not clearing empty slots in the array. E.g. by assigning Default(T) to them.

Why would those have to be cleared? One shoukdn't be able to read those out and I don't remember but if the buffer has to free any instances contained in it when the buffer is freed it will only free the instances still in the buffer.

Share this post


Link to post
9 hours ago, Stefan Glienke said:

No, yes

 

For managed types you can System.Move them in the internal array - however it also does it when peeking x items into the result array.

For types containing weak reference System.Move does not work even for the internal array.

Ok, I think I see what you're after. In case of the peek one would have to use the assignment operator then (if the type is a managed one) in order to increase the reference counter. Am I right? But how to find out whether the type is managed?

Share this post


Link to post
2 minutes ago, TurboMagic said:

Why would those have to be cleared?

Because otherwise the buffer will still hold a reference to the T instance. For any managed type this will be a problem.

 

For example what happens if T is an interface?

 

Maybe some unit testing is in order...

Share this post


Link to post
4 minutes ago, Anders Melander said:

Because otherwise the buffer will still hold a reference to the T instance. For any managed type this will be a problem.

 

For example what happens if T is an interface?

 

Maybe some unit testing is in order...

Thanks! That could be fixed at the place where items get taken out of the list. I guess one would have to make a distinction of cases via

IsManagedType(T) so one can keep using Move for non manages types and assignment operator for managed ones. Would that be correct?

 

Share this post


Link to post
19 minutes ago, Anders Melander said:

Because otherwise the buffer will still hold a reference to the T instance. For any managed type this will be a problem.

 

For example what happens if T is an interface?

 

Maybe some unit testing is in order...

Yes, unit tests for managed types would still have to be created. And yes one would have to do some for strings and interfaces as well as tey're of course managed as well.

I contributed this to the public because it will not help the community if one always consumes only without giving. That also means, if there's interest in this library others should contribute fixes etc. as well. My main open source commitment currently is DEC (Delphi Encryption Compendium) and that's enough work.

Edited by TurboMagic

Share this post


Link to post
2 minutes ago, TurboMagic said:

Would that be correct?

Move isn't the problem in this particular case. The problem is that once you logically remove an entry from the array then you need to finalize that entry in the array to clear the reference. You can do that by assigning Default(T) to the entry.

Share this post


Link to post
1 minute ago, Anders Melander said:

Move isn't the problem in this particular case. The problem is that once you logically remove an entry from the array then you need to finalize that entry in the array to clear the reference. You can do that by assigning Default(T) to the entry.

Ok, thanks for this hint.

Share this post


Link to post
1 hour ago, TurboMagic said:

Since I didn't hear from him with a ull request or any other "delivery" yet I guess he got stuck translating the comments...

Some things just need their time...

Share this post


Link to post

Ok, besides accepting Uwe's pull request I did some changes to the Peek method in order to make it more compatible with managed types. Feel free to look at it and critisise where necessary, I admit that I didn't test it yet (need to create unit tests) but it's getting late enough already. I can only learn from it.

And if somebody wants to contribute: feel free. As far as I understood Stefan, one could get rid of the 2nd class implemented for managed types altogether by using IsManaged and calling the appropriate code to release the items where necessary.

Share this post


Link to post

Access violation, but I don't know why.

Ok, I started to write some further unit tests now as a start to fix the issues this implementation has in order to learn some things.

I copied the integer unit tests which run fine and reworked those into string ones. so <T> is string now.

 

One of the tests calls this method:

 

function TRingbuffer<T>.Peek(Index: UInt32): T;
var
  reminder : UInt32;
begin
  if (Index < Count) then
  begin
    // Puffer läuft derzeit nicht über seine obere Grenze hinaus
    if ((FStart+Index) < Size) then
      result := FItems[FStart+Index]
    else
    begin
      // um wieviel geht es über die obere Grenze hinaus?
      reminder := (FStart+Index)-Size;
      result   := FItems[reminder];
    end;
  end
  else
    raise EArgumentOutOfRangeException.Create('Invalid Index: '+Index.ToString+
                                              ' Max. Index: '+Count.ToString);
end;

FItems at that point contains 5 items, FStart is 1 and Index is 1 as well.

It crashes with EInvalidPointer at this line:

 

result := FItems[FStart+Index]

 

When debugging the asm I see some call to freemem.

I would have expected that Peek would simply return a string with the contents of FItems[FStart+Index] and that it would increase the
reference counter of the string stored in FItems[FStart+Index].

 

This Peek method is called in a loop over the complete ringbuffer to check if its contents is the expected one.

For Index = 0 it doesn't crash.

 

What is wrong on my assumption?

And the other question would be: should peek increase reference counter of reference counted types (string, interface...) or return
a copy which is not reference counted and thus completely detached from the buffer inside the ring buffer class?

And if "detached" should be preferred, how to do the copying properly?

Share this post


Link to post

Defect is somewhere else and you messed up the string reference counting, if the error occurs on not the first call to Peek then obviously Result contains a prior string reference which the UStrAsg call that is generated for the assignment clears.

 

Did you fix procedure Add(Items:TRingbufferArray); already? Because that must not use Move for managed types

Edited by Stefan Glienke

Share this post


Link to post

I fixed the Add(Items:TRingbufferArray) now, it might need further test coverage for managed types, but that at least fixed some of the failed string test cases now.

Peek no longer crashes and while working on that I had see that Peek had already a value in Result at the beginning of the method. Trying to set that to Default(T)

there crashed immediately. So fixing add was the right thing.

 

One thing which still puzzles me and maybe is not even possible:

I can have such a generic ringbuffer class which works for non managed types and for reference counted types at the same time.

But I don't seem to be able to make it work with objects and OwnsObject semantics, as I cannot call free. I can only call free if I introduce a class constraint.

Is this assumption correct and my initial attempt with a class for objects inheriting from the first one is the right one?

 

I already tried to find out how TObjectList<T> from Generics.Collections does it, but I failed to find the free of the items in it...

Share this post


Link to post
if GetTypeKind(T) = tkClass then
  PObject(@item)^.Free;

RTL still uses DisposeOf (which you also need to if you want to support ARC before 10.4) - look into TObjectList<T>.Notify

Edited by Stefan Glienke

Share this post


Link to post

Small status update: it looks I have fixed all non object related issues. At least the unit tests for those do run and the same unit tests as implemented for unmanaged types have ben implemented for strings as well and they do run.

What's left now is the OwnsObjects semantics and tests for interfaces and regular classes. That's the state of the development branch.

Share this post


Link to post

I added unit tests for usage with objects now, testing the OwnsObjects semantics. After fixing a bug in destructor, where I tried to free one object too much (which even got the IDE into trouble)
it seems to work as it should.

 

But: I have a memory leak problem with two of the unit tests which I don't know how to fix.

These are unit tests testing exceptions and the program flow doesn't seem to get to the point in the test method after the exception has been raised.

So the code I put there for cleaning up seems not to be run.

 

The circular buffer doesn't free the objects in such an exception case either.

I thought that the user wouldn't expect me to do this. Or would a user expect me freeing

objects the user tried to add but couldn't because the buffer is full and my implementation has no "overwrite the oldest items in such a case" semantics?

(if I would be thinking about adding this I'd make it configurable)

Share this post


Link to post
On 8/24/2020 at 8:08 PM, Stefan Glienke said:

Leave implementing generic collections to people experienced with it (which I in no way claim to have monopoly on)

To be fair, there's a Catch-22 in that idea.   ie don't implement Generics until you have experience implementing Generics.

 

(and the same would apply for trying to use a c++ like move feature)

 

If someone publishes open source ... not part of a (reasonably big) commercial product like RAD ... and it is useful to maybe 80% of people, then sure it's valuable to point out edge cases - but it doesn't mean it should be discouraged.  We need *more* Delphi out there.  And more understanding of these elements that weren't even part of Delphi in say 2005.

  • Like 1

Share this post


Link to post

So have you looked at my newest commit? Did you find any failure in it? I'm asking because I'm tempted to "do a release"...

Share this post


Link to post

Today I fixed a few bugs regarding use for storing objects in the buffer in the Remove and Delete methods

and I fixed all memory leaks in the unit tests.

 

The GitHub repository is up to date. Does anybody spot any bugs I have missed?

Or is the source now "ok" so that the public should be "safe" when using it?

  • Like 1

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×