3 ms·

> So, you did tests to show that linked lists are slower AND use more memory? Which we both already knew? Why? I showed you that it often does not matter much.

by lispm 2y ago

> So, you did tests to show that linked lists are slower AND use more memory? Which we both already knew? Why? I showed you that it often does not matter much. > Oh good, I'll keep that in mind for the next time I am forced to prepend a bunch of items to a list, which I expect to happen approximately 0 times before I die of old age. It's not that uncommon, for example for a simple stack implementation. > So... what I'm hearing here is, that no, you aren't capable of admitting that Lisp has faults. With this discussion style you won't get very far. > It seems to me that being slower and using more memory and getting nothing in return isn't a tradeoff. Right, I think that's a useful task for you to actually think about: what do we get in return? Why does Haskell use linked lists? Why does INRIA's OCAML ( https://ocamlbook.org/lists-and-structural-recursion/ https://ocamlbook.org/lists-and-structural-recursion/ ) ? Why does Microsoft's F# ( https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/lists https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref... ) ? Why does Ericsson's Erlang ( https://www.erlang.org/doc/system/listhandling.html https://www.erlang.org/doc/system/listhandling.html ) ?

kerkeslager 2y ago
> I showed you that it often does not matter much. ...which we also both already knew. The thing is, it does matter sometimes; often enough that there's no good reason to take the less performant route by default. > > Oh good, I'll keep that in mind for the next time I am forced to prepend a bunch of items to a list, which I expect to happen approximately 0 times before I die of old age. > It's not that uncommon, for example for a simple stack implementation. 1. Does Lisp not come with a stack implementation? In general, I do not plan to implement simple stacks. 2. Pushing items onto a stack isn't inherently a prepend operation. It's generally a "put it on an end" operation, meaning you could append it. Now, with a linked list that would be slower, so obviously you prepend if you're using a linked list, but if you're using a vector, you append. And, lo and behold, appending-vector-based stack performs better than a prepending-linked-list-based stack, because cache. So if I do implement a simple stack, I implement it with a vector (example[1]). I'm a professional. I'm not writing high school CS level demo programs. If I need a stack, I'm generally using the standard implementation that ships with the language, and if the language doesn't have one, I implement a stack with a vector because there's no upside to implementing it as a linked list. So no, it's not common to prepend to a list, and unless your language is intended for writing high school CS level programs, it probably shouldn't prominently feature linked lists as a normal way to do things, and if it does, that's a problem. Not a tradeoff, because you're not getting anything in return. A problem. > > So... what I'm hearing here is, that no, you aren't capable of admitting that Lisp has faults. > With this discussion style you won't get very far. And how far has your jumping in to defend Lisp and never admitting it has any faults gotten you? > Right, I think that's a useful task for you to actually think about: what do we get in return? Nothing I need or want. Yes, I know the answer you're fishing for is "immutability" but the fact is if you're operating on lists as a whole, i.e. your map/reduce/etc. type operations, you can achieve immutability with vectors, and it will be more performant when you do so. > Why does Haskell use linked lists? > Why does INRIA's OCAML ( https://ocamlbook.org/lists-and-structural-recursion/ https://ocamlbook.org/lists-and-structural-recursion/ ) ? > Why does Microsoft's F# ( https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref... ) ? > Why does Ericsson's Erlang ( https://www.erlang.org/doc/system/listhandling.html https://www.erlang.org/doc/system/listhandling.html ) ? Because all these languages are wearing the same FP blinders as Lisp. Why aren't any of these languages popular? ;) [1] https://craftinginterpreters.com/a-virtual-machine.html#the-vms-stack https://craftinginterpreters.com/a-virtual-machine.html#the-...
- lispm 2y ago
  > Pushing items onto a stack isn't inherently a prepend operation. a stack has no idea of "prepend" or similar. It's defined by abstract like operations PUSH, POP, IS-EMPTY, MAKE-STACK. How it is implemented is an implementation detail. > It's generally a "put it on an end" operation, Which you made up. There is nothing "generally" like that. > meaning you could append it. Now, with a linked list that would be slower, and to append would be unnecessary. > So if I do implement a simple stack, I implement it with a vector (example[1]). That's a simple "bounded" & "fixed size" stack. > I'm a professional. Okay. ;) > Yes, I know the answer you're fishing for is "immutability" That would be one answer. Can you think of more?
  - kerkeslager 2y ago
    > > Pushing items onto a stack isn't inherently a prepend operation. > a stack has no idea of "prepend" or similar. It's defined by abstract like operations PUSH, POP, IS-EMPTY, MAKE-STACK. How it is implemented is an implementation detail. You say that as if the fact that it's an implementation detail means it doesn't matter. Implementation details do, in fact, matter. > > It's generally a "put it on an end" operation, > Which you made up. There is nothing "generally" like that. So you're saying that stacks don't have a "push" operation? Or that you don't understand what "push" does? > > meaning you could append it. Now, with a linked list that would be slower, > and to append would be unnecessary. Literally picking and quoting parts of two sentences out of context to state the obvious as if it's a response to anything I said in context is a new low even for you. > > So if I do implement a simple stack, I implement it with a vector (example[1]). > That's a simple "bounded" & "fixed size" stack. No, it's not. Are you aware that vectors can be resized? > > Yes, I know the answer you're fishing for is "immutability" > That would be one answer. Can you think of more? I'm not going to make your argument for you. If you have something to say, say it.
- kazinator 2y ago
  It took me about a minute to find an instance of list linking in Java sources (OpenJDK): class JVMCIRuntime: public CHeapObj<mtJVMCI> { ../ JVMCIRuntime* _next; The Linux kernel has list linking all over the place. Userland libraries and utilities ditto. I don't think I've ever worked on a C++ or C project that had no linked lists anywhere. I'm trying to think of an example but coming up blank. Quite often but not always linked lists in C are intrusive. Certain object are going to be put into exactly one list. Or more than my list but only one at a time. So the link pointer or pointers are embedded into that object. And so no memory allocation is required to insert those objects into a list. A classic example of this is putting a process structure onto a scheduling queue. You would never want a vector for this, for reasons that a professional such as yourself should understand.

by lispm 2y ago

kerkeslager 2y ago

> I showed you that it often does not matter much. ...which we also both already knew. The thing is, it does matter sometimes; often enough that there's no good reason to take the less performant route by default. > > Oh good, I'll keep that in mind for the next time I am forced to prepend a bunch of items to a list, which I expect to happen approximately 0 times before I die of old age. > It's not that uncommon, for example for a simple stack implementation. 1. Does Lisp not come with a stack implementation? In general, I do not plan to implement simple stacks. 2. Pushing items onto a stack isn't inherently a prepend operation. It's generally a "put it on an end" operation, meaning you could append it. Now, with a linked list that would be slower, so obviously you prepend if you're using a linked list, but if you're using a vector, you append. And, lo and behold, appending-vector-based stack performs better than a prepending-linked-list-based stack, because cache. So if I do implement a simple stack, I implement it with a vector (example[1]). I'm a professional. I'm not writing high school CS level demo programs. If I need a stack, I'm generally using the standard implementation that ships with the language, and if the language doesn't have one, I implement a stack with a vector because there's no upside to implementing it as a linked list. So no, it's not common to prepend to a list, and unless your language is intended for writing high school CS level programs, it probably shouldn't prominently feature linked lists as a normal way to do things, and if it does, that's a problem. Not a tradeoff, because you're not getting anything in return. A problem. > > So... what I'm hearing here is, that no, you aren't capable of admitting that Lisp has faults. > With this discussion style you won't get very far. And how far has your jumping in to defend Lisp and never admitting it has any faults gotten you? > Right, I think that's a useful task for you to actually think about: what do we get in return? Nothing I need or want. Yes, I know the answer you're fishing for is "immutability" but the fact is if you're operating on lists as a whole, i.e. your map/reduce/etc. type operations, you can achieve immutability with vectors, and it will be more performant when you do so. > Why does Haskell use linked lists? > Why does INRIA's OCAML ( https://ocamlbook.org/lists-and-structural-recursion/ https://ocamlbook.org/lists-and-structural-recursion/ ) ? > Why does Microsoft's F# ( https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref... ) ? > Why does Ericsson's Erlang ( https://www.erlang.org/doc/system/listhandling.html https://www.erlang.org/doc/system/listhandling.html ) ? Because all these languages are wearing the same FP blinders as Lisp. Why aren't any of these languages popular? ;) [1] https://craftinginterpreters.com/a-virtual-machine.html#the-vms-stack https://craftinginterpreters.com/a-virtual-machine.html#the-...

lispm 2y ago
> Pushing items onto a stack isn't inherently a prepend operation. a stack has no idea of "prepend" or similar. It's defined by abstract like operations PUSH, POP, IS-EMPTY, MAKE-STACK. How it is implemented is an implementation detail. > It's generally a "put it on an end" operation, Which you made up. There is nothing "generally" like that. > meaning you could append it. Now, with a linked list that would be slower, and to append would be unnecessary. > So if I do implement a simple stack, I implement it with a vector (example[1]). That's a simple "bounded" & "fixed size" stack. > I'm a professional. Okay. ;) > Yes, I know the answer you're fishing for is "immutability" That would be one answer. Can you think of more?
- kerkeslager 2y ago
  > > Pushing items onto a stack isn't inherently a prepend operation. > a stack has no idea of "prepend" or similar. It's defined by abstract like operations PUSH, POP, IS-EMPTY, MAKE-STACK. How it is implemented is an implementation detail. You say that as if the fact that it's an implementation detail means it doesn't matter. Implementation details do, in fact, matter. > > It's generally a "put it on an end" operation, > Which you made up. There is nothing "generally" like that. So you're saying that stacks don't have a "push" operation? Or that you don't understand what "push" does? > > meaning you could append it. Now, with a linked list that would be slower, > and to append would be unnecessary. Literally picking and quoting parts of two sentences out of context to state the obvious as if it's a response to anything I said in context is a new low even for you. > > So if I do implement a simple stack, I implement it with a vector (example[1]). > That's a simple "bounded" & "fixed size" stack. No, it's not. Are you aware that vectors can be resized? > > Yes, I know the answer you're fishing for is "immutability" > That would be one answer. Can you think of more? I'm not going to make your argument for you. If you have something to say, say it.
kazinator 2y ago
It took me about a minute to find an instance of list linking in Java sources (OpenJDK): class JVMCIRuntime: public CHeapObj<mtJVMCI> { ../ JVMCIRuntime* _next; The Linux kernel has list linking all over the place. Userland libraries and utilities ditto. I don't think I've ever worked on a C++ or C project that had no linked lists anywhere. I'm trying to think of an example but coming up blank. Quite often but not always linked lists in C are intrusive. Certain object are going to be put into exactly one list. Or more than my list but only one at a time. So the link pointer or pointers are embedded into that object. And so no memory allocation is required to insert those objects into a list. A classic example of this is putting a process structure onto a scheduling queue. You would never want a vector for this, for reasons that a professional such as yourself should understand.