Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #31090

Re: "null", polymorphism and TCO

Show all headers | View raw

On 08.02.15 19.16, Stefan Ram wrote:
[Linked List]
>    Neither null nor java.util.Optional is needed when one
>    is using polymorphism, i.e., real OOP. We just need to say
>    that an entry with a next entry is a different type than
>    an entry without a next entry. No »null«, no »Optional«,
>    just polymorphism!
>
> abstract class Entry
> { java.lang.String text;
>    abstract void accept
>    ( java.util.function.Consumer< java.lang.String >consumer );  }
[...]

Introducing run time polymorphism into this trivial use case can cause a 
large performance impact. Mainly because the JIT no longer can inline 
trivial functions like accept, but additionally because the virtual call 
discards the CPU pipeline on many platforms. In contrast the conditional 
branch of the null check can be handled by the branch prediction with a 
reasonable hit rate.
It is like to break a nut with a sledgehammer.

You already mentioned the need for tail call optimization, witch in not 
that trivial with languages that guarantee access to the call stack by 
reflection.
But there are further disadvantages. E.g. the property to be a 
TerminationEntry is no constant of time. Appending and removing Elements 
at the end of the List now requires reallocation of another element to 
change its type. Moving elements in the list to or from the end too.
And last but not least linked lists usually guarantee the validity of 
iterators during list modification unless the current element is 
removed. You proposal breaks with this rule.

The situation might be different if we would be talking about a language 
that can subclass existing objects. In this case TerminationEntry might 
turn into a ContinuationEntry and reverse. However, most (or all?) 
existing hardware cannot deal with runtime subclassing efficiently.

>    From a practical point of view, the null solution
>    seems to be a kind of optimization: When one wants
>    to append to a TerminationEntry, one first needs to
>    replace it by a ContinuationEntry. This wastes more
>    resources than just overwriting a null value.

Not really. One machine size word per non empty list is really not that 
much. And you need the null check for the root anyway or do you propose 
to create a polymorphic list class for an empty list also. This would 
have funny side effects, like that append needs to return a new list on 
addition of the first argument.

If you really want to save resources with linked lists then you should 
allocate Entry objects that can hold more than one logical entry. 
Unfortunately the java language is very well suited for tricks like this 
because it does not allow inline arrays of constant size.

If you want to count clock cycles and memory bytes with an OOP language 
you should move to C++. It is much closer coupled to the hardware and 
allows really many hard tricks without loosing type safety and OOP style.


Marcel

Back to comp.lang.java.programmer | Previous | Next | Find similar | Unroll thread

Thread

Re: "null", polymorphism and TCO Marcel Mueller <news.5.maazl@spamgourmet.org> - 2015-02-08 23:14 +0100

csiph-web