This is a straw-man argument. Yes, it's true that a linked list isn't inherently parallelisable, and yes it's not the the structure I'd choose if I wanted to use as many cores as possible when sorting a single list, or converting it to uppercase, etc. etc. As a counterpoint, many fork-join approaches can benefit from TCO, and fork-join *is* an effective technique for performing parallel operations within a single data structure.
But even in a highly concurrent application, linked-lists can make sense when working with a great many of them. It's a particularly lightweight and *immutable* structure, which makes it especially suited for passing around between threads/actors/whatever. If I'm serving up the same list of names to two web clients, and one of them wants it converted to uppercase, then there's no risk of accidentally mutating the list that the other client wants. Nor do I have to worry about ConcurrentModification exceptions - so I'm also avoiding a try/catch block. I'm reminded of the oft-quoted example about adding people to a project: "You can't use 9 women to make a baby in one month". This is true, but it's also a perfect textbook case of what to do if you want to make as many babies as possible within 9 months... *none* of this is specific to Scala of course. It's not even specific to functional programming per-se, as both immutable structures and recursion are useful techniques even if you don't have functions as first class entities (the reverse isn't true, I'd find it hard to do functional programming without immutability). The single-entry-single-exit principle that you malign as being the product of a "Scala Junkie" was first established in the 60s, as part of Dijkstra's structured programming, though I'm not lost on the irony that structured programming really came to light with his famous "goto statement considered harmful" letter, whereas TCO is typically implemented as a goto (behind the scenes though, where it isn't harmful). p.s. A immutable linked-list is just a series of "cells", each one holding a value and the rest of the list. All except the last one. Unless your mention of "tracker objects" is simply a synonym for these tail objects, then I suspect you may have misunderstood how the structure is implemented. On Monday, 23 July 2012, Reinier Zwitserloot wrote: > I find it absolutely hilarious that you mention linked lists in the same > breath as the need to work with multicore processors. You realize that > linked lists, by their very nature, are 100% impervious to parallelizing? > At least with array lists you can split em up into blocks and hand off each > block. Scala and/or functional programming aren't some sort of magic faerie > dust that makes everything work just peachy in multicore world. Splitting > jobs at the highest of levels, there's your magic faerie dust. Fortunately > it's something your web servlet dispatcher is probably already doing for > you. Yay for frameworks. > > On Monday, July 23, 2012 12:31:44 AM UTC+2, KWright wrote: >> >> It's not just the methods, it's the data structures. For example, >> recursion makes a LOT of sense for iterating over an immutable linked list, >> and is often one of the first techniques taught within LISP. The need >> seems less apparent in an imperative/mutable paradigm, but I think it's >> fair to predict that we'll see less and less of this style as core counts >> follow the inevitable curve of Moore's law and as technologies like OpenCL >> become integrated into the Java ecosystem (NVidia's flagship GTX 690 has >> 3072 cores, and we're seeing this tech creeping back into CPUs...) >> >> > >> Only if tools are not adapted to show the presence of TCO in a stack >> trace. Which seems highly unlikely if this becomes a core JVM optimisation. >> >> > This kind of complication is exactly why it's not worth it. It's not a > simple matter of finding 'blank' calls into another method and replacing > the subroutine call with a 'ditch my frame, then goto' approach. > > >> >> >>> * Resource Management (i.e. try/finally blocks) instantly kill TCO. The >>> requirement that some method remains TCOable is a gigantic pain in the >>> behind for code maintainers. >>> >> >> Try/finally blocks mess with almost any declarative/parallel technique >> available. This is why Scala has `Either`, Haskell has `Maybe` and Akka's >> futures will trap and return an Exception instead of throwing it. >> > > Yet more distracting bullpucky on how parallel programming is somehow > forcing us into doing entirely different things. try/finally isn't going > away - resources need managing, period. There's no link between TCO and > parallelism, no matter how much you try to make one. Languages which > traditionally have looked at the functional approach have also tended to > like TCO. Similarly, recursion is still completely irrelevant here. If I > want to, for example, optimize the ability to let's say determine the > maximum value in a list (using multiple cores), I'd write something like: > > int maxVal = myList.par().reduce(Aggregates::max); > > two observations: > > (A) What in the flying blazes does this have to do with recursion and TCO? > > (B) I sure hope that myList is NOT a linked list, because if it was, > performance is going to suck. > > Do you have clue as to why a linked list is just end of the line, > performance wise? How crazy you sound here? The tracker objects of a linked > list are just _HORRIBLE_ from a modern CPU architecture point of view, and > any data structure which can only be traversed accumulation style is the > WORST possible thing you could ever have for a parallelism point of view. > It needs to be trivially easy to take any given data structure and split it > into X roughly equal pieces. Assuming each piece is itself such a data > structure, you can hardcode X to any value you please so long as it is > larger than 1. For example, a conclist is trivially splittable into 2 > roughly equally sized conclists. To parallelize a job on a conclist, you > check if you are the singleton or void list and return the appropriate > number, and if not, you ask your left child to go figure out the answer for > itself in a separate thread, and then you ask the right side to go figure > out the answer in this thread, then when that returns you wait for left, > and then you can trivially provide an answer. conslists (i.e. LinkedLists) > are not trivially splittable into 2 batches. They are therefore stupid, > from a parallelism perspective. > > > >> >>> Not least, the `return` statement itself. In almost all function >> languages the final expression evaluated in a function becomes the return. >> More than anything else, I've found this makes it far easier to reason >> about what can (and what can't) be optimised using tail-calls. >> >> > Yes, you are a scala junkie. No, this STILL doesn't mean that the rest of > the java community thinks like you. Which part of: The current crop of java > programmers do not think like you, and do not understand what is and is not > TCO-able, is hard to understand? > > -- > You received this message because you are subscribed to the Google Groups > "Java Posse" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/javaposse/-/DRqmKhIqs44J. > To post to this group, send email to > [email protected]<javascript:_e({}, 'cvml', > '[email protected]');> > . > To unsubscribe from this group, send email to > [email protected] <javascript:_e({}, 'cvml', > 'javaposse%[email protected]');>. > For more options, visit this group at > http://groups.google.com/group/javaposse?hl=en. > -- Kevin Wright mail: [email protected] gtalk / msn : [email protected] quora: http://www.quora.com/Kevin-Wright google+: http://gplus.to/thecoda <[email protected]> twitter: @thecoda vibe / skype: kev.lee.wright steam: kev_lee_wright "My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra -- You received this message because you are subscribed to the Google Groups "Java Posse" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/javaposse?hl=en.
