The list or vector is 10000 elements long and 100 times reversed and the difference in runtime is tiny. The list version is only marginally slower, but allocates a lot more memory.
I can also construct cases, where the list is much faster. Adding a one element list/vector to the front:
CL-USER 22 > (time (test1 10000 100))
Timing the evaluation of (TEST1 10000 100)
User time = 0.016
System time = 0.000
Elapsed time = 0.012
Allocation = 9148776 bytes
0 Page faults
GC time = 0.000
#(A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ...)
CL-USER 26 > (time (test2 10000 100))
Timing the evaluation of (TEST2 10000 100)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 1042248 bytes
0 Page faults
GC time = 0.000
(A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ...)
Here the runtime for lists is much faster, since it does not copy the complete list or -> lists share storage, consing to the front is cheap.
-> for many practical use cases for lists the total runtime and the runtime difference does not matter
Obviously there are also many case where a list would perform much worse, like accessing the last element of a list.
> Are you even capable of admitting that Lisp has serious faults
You seem to be keen to find "faults". Usually things are not black and white. There is no true and false, but engineering trade-offs. These tradeoffs can Lisp make the wrong choice for problems. Many of the trade-offs are also influenced by non-technical issues: like the amount of engineering time invested into a language implementation: see SUN/Oracles investment into Java.
So, you did tests to show that linked lists are slower AND use more memory? Which we both already knew? Why?
> I can also construct cases, where the list is much faster. Adding a one element list/vector to the front:
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.
> > Are you even capable of admitting that Lisp has serious faults
> You seem to be keen to find "faults". Usually things are not black and white. There is no true and false, but engineering trade-offs. These tradeoffs can Lisp make the wrong choice for problems. Many of the trade-offs are also influenced by non-technical issues: like the amount of engineering time invested into a language implementation: see SUN/Oracles investment into Java.
So... what I'm hearing here is, that no, you aren't capable of admitting that Lisp has faults.
I'm aware that tradeoffs exist. I'm also aware that faults exist. These two can both be true.
It seems to me that being slower and using more memory and getting nothing in return isn't a tradeoff.
> 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?
> 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.
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.
> Quite often but not always linked lists in C are intrusive.
Yes, and that's a significantly different data structure from a cons-cell based list, so I don't think it's particularly relevant. C and C++ certainly aren't examples of one of the languages lispm is claiming uses the Lisp model.
> And so no memory allocation is required to insert those objects into a list.
This is a pretty key distinction which doesn't apply to the linked list objects I'm talking about.
Let's not pretend this proves your point in any way. Intrusive lists in a manually managed memory system are incomparable to the cons cell based linked lists in a garbage collected system which you're defending. This is particularly true when the intrustive lists require no memory allocation.
> 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"
> > 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.
Let's see, I have here a Common Lisp compiling to machine code, here non-optimized generic Lisp code:
I'm allocating n elements list/vector of vectors and reverse it p times. reversing allocates a new list/vector.
The list or vector is 10000 elements long and 100 times reversed and the difference in runtime is tiny. The list version is only marginally slower, but allocates a lot more memory.I can also construct cases, where the list is much faster. Adding a one element list/vector to the front:
Here the runtime for lists is much faster, since it does not copy the complete list or -> lists share storage, consing to the front is cheap.-> for many practical use cases for lists the total runtime and the runtime difference does not matter
Obviously there are also many case where a list would perform much worse, like accessing the last element of a list.
> Are you even capable of admitting that Lisp has serious faults
You seem to be keen to find "faults". Usually things are not black and white. There is no true and false, but engineering trade-offs. These tradeoffs can Lisp make the wrong choice for problems. Many of the trade-offs are also influenced by non-technical issues: like the amount of engineering time invested into a language implementation: see SUN/Oracles investment into Java.