LinkedList pointer implementation gives bad results!

[Giorgi Chapidze 2]

Hi! I am new to Delphi, but I think I am getting something done! I am not quite sure what I am doing wrong, but this should be correct in Java! I have the corresponding results shown in the debugger at the third iteration!

 

Can anyone point out what I am doing wrongly? (Source Code: MyCollections.pas)

 

Edited April 7, 2023 by Giorgi Chapidze

[Anders Melander 1783]

I would really suggest that you postpone messing with pointers until you have a better understanding of the language. Use an array or a TList instead; They perform better.

Also, objects aren't really suited for double-linked lists as you will need a full (but empty) object for the head node.

 

That said, the problem appears to be that you aren't aware that an object reference is itself a pointer and that local variables are temporary and allocated on the stack.

Thus...

Tmp^.Next := @Node 

...assigns the address of the Node pointer (and not the address of the Node object) to the Next field.

The correct statement would look more like this:

Tmp.Next := Node;

Notice that the dereference operator (^) is optional so I didn't use it. I think it often just makes the code harder to read.

[Giorgi Chapidze 2]

Thanks for reply!  Yes, you have noticed correctly; I was thinking in Java's terms. I really should learn the language first!

[David Schwartz 426]

There's been very little need for pointers in Delphi after they made it so objects are implicitly passed by reference. 

 

People still use them with Record types.

 

As an aside, I've been working with TMS WEB Core a lot lately. It transpiles the Dephi code to javascript, and js doesn't support pointers. So it won't compile Delphi code that uses pointers. Aside from the fact that TTreeNode's have a Data property that's typed as Pointer, I've not had any problem at all. 

 

I urge you to learn what's in the RTL and how Generic collections work rather than reinventing the wheel. There are far more interesting problems you can explore besides data structures invented at a time when CPU cycles and memory were very expensive compared to the cost of programmer time.

 

The most commonly used class in Dephi is the TStringlist. It's like the "Swiss Army Knife" of most Delphi programming. Spend time playing with every property it has and get to know it inside and out; I promise you it will be time far better spent than messing with basic data structures. BTW, something not a lot of Dephi programmers know is that a TStringlist can be used to manipulate CSV files directly. You can make them multi-dimensional by hanging them off of the Objects property in a base object. You can also make a wrapper class that defines properties to make it much simpler to access things stuffed into those Objects 'arrays'. 

 

When I was learning C++, there was a book, "C++ Idioms" that I referred to a lot to learn different types of common coding idioms and patterns. A lot of them are really OOP patterns that apply in many languages, although many are specific to C++. 

 

Spend time learning Delphi programming idioms, especially the different ways of declaring properties and when it's good to access local fields directly rather than setting every property up to use getter and setter methods. 

 

And avoid getting into the habit of putting business logic inside of event handlers! Make a separate method that's called if you need to interact with other UI objects as a result of an event being triggered.

[Anders Melander 1783]

8 hours ago, David Schwartz said:

There's been very little need for pointers in Delphi after they made it so objects are implicitly passed by reference.

Object references are pointers. That was the whole point and the failure to understand that was the cause of the problem.

Apart from that, I agree that most people probably rarely, if ever, use them directly.

 

8 hours ago, David Schwartz said:

There are far more interesting problems you can explore besides data structures invented at a time when CPU cycles and memory were very expensive compared to the cost of programmer time.

Sure but it's an important data structure to know. Would you hire a developer who couldn't create a linked list? I know I wouldn't.

 

8 hours ago, David Schwartz said:

The most commonly used class in Dephi is the TStringlist.

That really depends on what you do and how you do it. Common? Yes. Most common? Not a chance.

I can't remember when I last used a TStringList and I do a lot of string processing and UI stuff. I certainly wouldn't use it to handle CSV files. There's far too much of the format it can't handle properly.

 

8 hours ago, David Schwartz said:

And avoid getting into the habit of putting business logic inside of event handlers!

While I agree with this, it's not advice I would give a beginner. There are more important things to learn in the beginning and that one will just get in the way of that.

[David Schwartz 426]

4 hours ago, Anders Melander said:

Sure but it's an important data structure to know. Would you hire a developer who couldn't create a linked list? I know I wouldn't.

I have never seen a project fail because someone did not understand some fundamental data structure. However, I've seen plenty fail because they cannot listen to users and document what they said they wanted; because they cannot write clear specs that don't have holes in them; because they can't write code without making assumptions about edge cases because they're afraid to let their boss or client know there's still stuff they're unclear about; and I've seen lots of wasted efforts because even though we implemented exactly what the client asked for, when they saw it actually run, they decided it was totally useless -- because management refused to allow us to get into any kind of dialog with the clients to help clarify their actual use case needs.

 

As a point of fact, very few people I've met who were "self-taught" have ever had any exposure to fundamentals like what we learned in core Computer Science classes. Nonetheless, an increasing number of companies are now hiring people with degrees in English Lit, History, and Psychology, and teaching them how to program.

 

I've been wondering for a while now how relevant the core parts of most CS curricula are since most of it was an outgrowth of an era when both CPU cycles and memory space were far more expensive than programmer time. It's a sad fact that too many programmers with CS degrees will sit down and write a sort routine themselves rather than use a library, mainly because they just don't know what's available in the various libraries they have access to.

 

(In college, we were given bonus points for writing code that had fewer lines and/or took less memory space that the average. We were not rewarded for completing assignments quickly and completely using whatever tools we could find. "Time-to-market" is a very important metric for most companies that rely on software; it's also antithetical to what's taught in most CS programs.)

 

In fact, I'd be far more concerned about a job candidate who didn't know there are generics for all sorts of containers than whether they know how to implement a single- or doubly-linked list in Pascal. Sorry. 

 

I don't know how many times someone might think they need to implement a linked-list from scratch; but there have been plenty of times when I was told to do something within a time-frame that would be undoable if I had to rely on core concepts I learned in school rather than specialized libraries that would let me solve the problem in a fraction of the time.

 

So we can agree to disagree on this stuff.

[Lars Fosdal 1792]

Deviating slightly from the original topic: I wonder when green computing will become a part of education and business, i.e. writing code / designing libs that are less expensive in the context of power consumption.  

[Fr0sT.Brutal 900]

1 hour ago, Lars Fosdal said:

Deviating slightly from the original topic: I wonder when green computing will become a part of education and business, i.e. writing code / designing libs that are less expensive in the context of power consumption.  

Never. Why? Mining.

I doubt all bad algo's in the world together eat as much power as mining.

Edited April 10, 2023 by Fr0sT.Brutal

[Giorgi Chapidze 2]

Thank you all for your time and responses. I have taken notes on David's response, and I will set these things as TODOs in my free time. I have understood the pointers and implemented LinkedList and BST from scratch(thanks to Anders)... So as I understood, pointers are not used that much and references are used for higher level abstraction, as in Java? I am currently studying compiler design at the university and am going to build a simple one in Delphi.

By the way, can anyone suggest material on assembly in Delphi? Is it pure X64 assembly or sort of dialect, specific to Delphi?

Edited April 10, 2023 by Giorgi Chapidze

[Lars Fosdal 1792]

ASM is pretty much straight ASM32 or ASM64.

[David Schwartz 426]

16 hours ago, Giorgi Chapidze said:

So as I understood, pointers are not used that much and references are used for higher level abstraction, as in Java?

Pointers are used a LOT in Delphi, they just don't _look_ like it. I don't know about Java, but in C++ and Delphi, references are things that tell the compiler it's a Pointer that is automatically de-referenced so you don't need to add any sort of syntactical sugar to do it yourself. I simplifies writing code. I'm not sure I'd go as far as saying it "used for higher level abstraction". 

 

In C++ you get the same effect defining parameters on functions as references (eg., "int & abc" as opposed to "int * xyz"). Inside of the function, you'd refer to the contents of abc by simply saying "int x = abc" but for xyz you'd say "int x = *xyz". If you have a bunch of references in a nest of classes in C++,  you might see "x = aa.bb.cc.dd" whereas if they were pointers the line might be written as "x = aa->bb->cc->dd". The difference is only in how the code is written, and the fact that references cannot be treated like pointers. Same in Delphi: vars that refer to instances of classes are all "pointers", as opposed to vars that refer to record types. That is, classes automatically use pass-by-reference semantics while everything else is pass-by-value. 

 

When I started using C++, I found references to be quite refreshing to use because most of the time they simplified the code. I loved Delphi for the same reason -- allocating records and manipulating them in Pascal was always confusing to me. The implicit use of references for class types makes programming in Delphi a lot simpler than if you have to explicitly use Pointers and all of their associated syntactical sugar.

 

In the last version of TurboPascal (TP7 IIRC), they introduced something called "object" that was similar to a "class". I _think_ that's when they introduced the use of references in the compiler so when you had something defined as type "object" that told the compiler it was a pointer but you didn't need to use the ^ thingie to dereference it. They get ugly (and confusing) pretty quickly, as can be seen in C++ when you use pointers.

 

Delphi was originally supposed to be TP8, but they changed the name. Delphi introduced a "class" and everything defined as such was in fact derived from this base object called TObject. If you say, "type abc = class ... end;" it means the same as "type abc = class(TObject) ... end;". Also, in Delphi, anything derived from TObject (meaning it's a "class") is assumed to be a Pointer and is automatically de-referenced by the compiler to simplify the code. That's not true of "object" types. The old "object" type is still there, AFAIK, but it's more like C++ classes in that respect -- that is to say, they aren't derived from anything by default.

 

As far as compiler design goes, you'll learn there are mainly two types: a table-driven parser that uses a lexer in front, and a recursive-descent parser (which is how Pascal was originally designed to be parsed). Delphi will work for either one, but the tools used to generate code for lexers and parsers today generally don't give you Pascal as an option.

 

Just remember that compilers are just fancy Finite State Machines (FSMs). You might never have the need to build a lexer and parser for anything, or even a recursive-descent parser, but it's very likely you WILL run into situations where a FSM is the best tool for a particular job. (I hate it when people say, "I've never written a compiler in 30 years!" and I ask, "Well, how many times have you implemented complex control apps using FSMs?" and they usually say, "Well, ... quite a few.")

[Fr0sT.Brutal 900]

19 hours ago, Giorgi Chapidze said:

So as I understood, pointers are not used that much and references are used for higher level abstraction, as in Java?

Until Delphi implements array/string slices, pointers will rule in data processing that is supposed to be slightly faster than a snail.

Edited April 11, 2023 by Fr0sT.Brutal

[David Heffernan 2345]

1 hour ago, Fr0sT.Brutal said:

Until Delphi implements array/string slices, pointers will rule in data processing that is supposed to be slightly faster than a snail.

Indexing is fast 

[Brandon Staggs 278]

On 4/10/2023 at 4:50 AM, Lars Fosdal said:

Deviating slightly from the original topic: I wonder when green computing will become a part of education and business, i.e. writing code / designing libs that are less expensive in the context of power consumption.  

Hopefully never. Also unnecessary, even if you are one who buys into the ideology; go back 30 years and run machine code on the original hardware that ran it (C64, whatever). Running it in an emulator now will use so much less energy that you can do it without budging the needle on the phone battery in your pocket, even with all the overhead of emulation. My point is not that inefficient code is okay, but that worrying about energy consumption is largely a waste of time. Hardware will solve that.

 

Also, don't use ChatGPT for anything if you care about energy usage. It's through the roof compared to simple web searches.

 

Having said that, I see a lot of stuff coming out of Microsoft about energy efficiency. Green leafs all over task manager, etc. But is there really much difference between that and general code efficiency?

Edited April 11, 2023 by Brandon Staggs
qualification. :-)

[Stefan Glienke 2002]

4 hours ago, David Heffernan said:

Indexing is fast 

It is and that is not the main purpose of using a linked list - a linked list shines when you often insert or delete entries because that is O(1) whereas using an array is O(n) because of the necessary move operation.

[Fr0sT.Brutal 900]

4 hours ago, David Heffernan said:

Indexing is fast 

Who talks about indexing? Sometimes you have a raw buffer and have to search inside it for something or compare current pointer with something.

[Stefan Glienke 2002]

57 minutes ago, Fr0sT.Brutal said:

Who talks about indexing? Sometimes you have a raw buffer and have to search inside it for something or compare current pointer with something.

I think this came as response to some general pointer-related comment and is quite OT to the original topic which was about linked list - but I agree - especially when dealing with string parsing and alike, naive code often is full of tiny substring allocations which could be avoided by similar approaches as .NET went with their Span<T> - using that throughout the runtime significantly improved performance in many areas. In Delphi code one typically uses PChar but that lacks a length limitation and routines that take that into account often have an additional len parameter which requires carrying around two distinct values which in fact belong together.

[David Heffernan 2345]

5 hours ago, Fr0sT.Brutal said:

Who talks about indexing?

You did

10 hours ago, Fr0sT.Brutal said:

Until Delphi implements array/string slices, pointers will rule in data processing that is supposed to be slightly faster than a snail.

 

[Anders Melander 1783]

21 hours ago, Stefan Glienke said:

a linked list shines when you often insert or delete entries because that is O(1) whereas using an array is O(n) because of the necessary move operation.

Always? I haven't done my own benchmarking but I thought arrays also outperformed linked lists for the simple search+insert/delete case:

https://kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/

(yes, I know it's about Java. potato, potato...)

 

I mostly use linked lists for stuff like MRU/LRU caches, and only because I haven't bothered learning a more suitable structure (for caches, that is).

[Stefan Glienke 2002]

47 minutes ago, Anders Melander said:

Always? I haven't done my own benchmarking but I thought arrays also outperformed linked lists for the simple search+insert/delete case:

https://kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/

(yes, I know it's about Java. potato, potato...)

No, not always - that's why it says "Measure, don't guess".

Anyway apart from being Java, that article is over 10 years old and things change - libraries get optimized (yes, even Java )

I have no idea how the various pieces at play are implemented in Java - so why don't you simply run your own benchmark?

 

I explicitly did not mention search but wrote insert or delete. I am well aware of the fact that access to contiguous memory is so much faster than random memory access that I know that if you add searching to the use case the more costly insert/delete can become totally irrelevant simply because the search is so much faster. Of course, usually, you don't just insert or delete to a linked list but also perform some search to determine the location where to insert or delete which is the reason why many benchmarks also include search.

 

47 minutes ago, Anders Melander said:

I mostly use linked lists for stuff like MRU/LRU caches, and only because I haven't bothered learning a more suitable structure (for caches, that is).

I know a lot of literature mentions using linked list + hashtable but I would probably simply use a queue or deque that is backed by a circular array buffer.

 

If there is anything to take away from the article you linked to then it is this:

 

Quote

However, doing the big O comparison is just pointless. Let me be repeat this:  It is pointless to compare algorithms that way.

[...]
Big-O notations tells nothing about how one algorithm fare against another algorithm. Big-O will only tell you how performance will degrade as n increases.

This is because it completely ignores constant factors. Constant factors are why often the fastest algorithms and data structures, in reality, are hybrids that combine different algorithms. IntroSort is a good example that combines QuickSort with InsertionSort (for small sizes) and switches to HeapSort for QuickSorts worse cases. If you would ask "Which is better: QuickSort or InsertionSort?" Many people would say "QuickSort" but the the fact is that it depends on the number of elements. Similar to the question "Which is faster: a hashtable or linear search in an array?" Again it depends on several factors: the number of elements, the expense of comparison and hashing, and the actual implementation of the hashtable.

 

And talking about the O(n) for inserting or deleting from a list. Here is a little benchmark and the results from Delphi 10.4 and 11.3:

program BenchListInsertDelete;

{$APPTYPE CONSOLE}

uses
  Spring.Benchmark,
  System.Generics.Collections;

procedure InsertDelete(const state: TState);
var
  list: TList<Integer>;
  i: Integer;
  _: TState.TValue;
begin
  list := TList<Integer>.Create;
  list.Capacity := 1000;
  for _ in state do
  begin
    for i := 1 to 1000 do
      list.Insert(0, i);
    for i := 1 to 1000 do
      list.Delete(0);
  end;
end;

begin
  Benchmark(InsertDelete, 'insert-delete').MinTime(2);
  Benchmark_Main();
  Readln;
end.

Delphi 10.4.2  
  
----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
insert-delete/minTime:2,000     223341 ns       223644 ns        11947


Delphi 11.3

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
insert-delete/minTime:2,000      41379 ns        41487 ns        68923

You can guess why that is 

Edited April 12, 2023 by Stefan Glienke