Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Functional languages should be so much better at mutation than they are

cohost.org

Post reply on HN
Print view View original

91–100 of 188 posts

Re: Functional languages should be so much better at mutation than they are

#91

Post by IshKebab »

tome wrote: post #83
astrange wrote: post #60

Earlier quoted context omitted.

Haskell almost seems like it was intentionally designed to perform poorly on real computers, primarily because of space leaks and secondarily because the non-strict evaluation gets compiled into a lot of function pointer jumps, which branch predictors hate. I think it's funny that they make you write linked list code as a metaphor for generators, but it seems like it should be the other way round. (Also, it has excep…

> (Also, it has exceptions which are a bad language feature, and typed throws which are a worse one.) Can you elaborate? You can't stop people simulating exceptions with sum types, and if you have exceptions, why wouldn't you want them to be typed?

Sum types aren't a simulation of exceptions.

Re: Functional languages should be so much better at mutation than they are

#92

Post by naasking »

kaba0 wrote: post #90
tome wrote: post #88

Earlier quoted context omitted.

> You're basically trading runtime efficiency for memory. What do you mean? Aren't GCs both less efficient at run time and use more memory?

They are massively faster (as in, has better throughput) than ref counting. See my previous comment for more details.

Faster than ref counting AND than manual memory management. Papers that have recorded the traces of memory allocation and liveness info and then replayed them using GC or by inserting manual new/free show GC has a throughput advantage here.

Re: Functional languages should be so much better at mutation than they are

#93

Post by mananaysiempre »

tome wrote: post #88
tsimionescu wrote: post #76

Earlier quoted context omitted.

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

> You're basically trading runtime efficiency for memory. What do you mean? Aren't GCs both less efficient at run time and use more memory?

Worst case, 2× is actually a steal compared to a non-moving allocator such as malloc/free or RC built on top of that, which cannot[1] do better than about 1 + ½log₂(largest allocation / smallest allocation). For example, if you have allocations from 1K to 16K bytes, any malloc/free implementation can require at least 3× the memory you actually use; if from 16 to 16K, 6×; etc.

At this point I must mention that paged memory can get you just enough movability that catastrophic fragmentation of this kind is avoided[2] with high probability. Paging tricks can be seriously expensive on a modern multicore processor, though, so I’m not sure this is the way forward. (The paper report only 1% perf overhead for Firefox; I don’t know if that means Firefox is less multithreaded than it could be or what.)

[1] https://www.sqlite.org/malloc.html

[2] https://github.com/plasma-umass/mesh

Re: Functional languages should be so much better at mutation than they are

#94

Post by tsimionescu »

tome wrote: post #88
tsimionescu wrote: post #76

Earlier quoted context omitted.

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

> You're basically trading runtime efficiency for memory. What do you mean? Aren't GCs both less efficient at run time and use more memory?

No, the more memory you give them, the more efficient they are, and generally they are much more efficient than an equivalent program using malloc() + free() for every piece of memory that gets allocated.

Take the extreme case of a program where every allocation is permanent. The GC allocation will be much much faster than malloc() (GC allocation is normally just bumping a pointer to the end of the heap, while malloc() typically does a lot more work to segregate objects by size etc), and collection will never run. So, overall, the program will be significantly faster.

Edit: More realistically, a program that typically produces 1:1 live mmeory:junk, but occasionally spikes, will consume 0 GC time in normal operation (the GC will just let the junk sit there), while free() needs to run on all that junk as soon as it was created, otherwise it leaks forever.

Also, the fact that GCs can defer collection to later than the object going out of scope can often make them more efficient than a traditional free(). For example, if you have a large graph data structure that is now junk, free() needs to do work that's O(size of graph) to free all the nodes. A copying collector, the most popular design, never even looks at the graph, so it frees it in O(1). Edit: of course, the converse is also true: if the graph survives N collections, the copying GC has to do O(N * size) work, where malloc()/free() do nothing at all.

Re: Functional languages should be so much better at mutation than they are

#95

Post by bmacho »

ufo wrote: post #38
RandomThoughts3 wrote: post #4

The article utterly falls apart in its first paragraph where it itself acknowledges that the whole ML family including Ocaml has perfect support for mutation, rightfully assume most Ocaml programmers would choose to not use it most of the time but then assume incorrectly that it’s because the language makes it somehow uneasy. It’s not. It’s just that mutation is very rarely optimal. Even the exemple given fails: > Fo…

One thing that many people miss is that Haskell's monadic style is a direct consequence of lazy evaluation. It all started because they thought lazyness was nice, and wanted to make a language that brought that front and center. But then they found out that they had to come up with a new way to do side-effects, because traditional side-effects don't work when the order of evaluation is unpredictable.

> One thing that many people miss is that Haskell's monadic style is a direct consequence of lazy evaluation. It all started because they thought lazyness was nice, and wanted to make a language that brought that front and center. But then they found out that they had to come up with a new way to do side-effects, because traditional side-effects don't work when the order of evaluation is unpredictable.

But this is not true, is it? I thought that Haskell solution for side effects was just tagging the functions with side effects, and make the compiler handle functions with side effects as regular programs, no laziness, no memoization, no reordering. 'Monad' is just a mathematical structure that regular programs obey, also 'do notation' is just a style that allows Haskell programmers to write imperative style code.

Re: Functional languages should be so much better at mutation than they are

#96

Post by naasking »

tsimionescu wrote: post #76
devit wrote: post #56

Earlier quoted context omitted.

You can, but it turns out that, as one may intuitively expect, a GC is never needed unless implementing a VM for a GC-based language or an API that required GC like fd passing on unix domain sockets, and those generally want an ad-hoc GC instead tailored to whatever you are implementing. Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential an…

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

> 2. GC performance is harder to predict and reason about than certain other allocation strategies

I'm not sure what you mean by this being the least understood. It seems like it's very well understood: GC introduces latency if you want good throughput, or it reduces throughput if you want excellent latency (sub-100us is possible).

Of course, that doesn't mean you can predict what specific throughput or latency properties your specific program will have, except for GCs that have maximum bounded latency guarantees.

Re: Functional languages should be so much better at mutation than they are

#97

Post by devit »

devbent wrote: post #77
tsimionescu wrote: post #76

Earlier quoted context omitted.

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

People often forget that the runtime of free is not trivially calculatable! I've worked on tiny embedded systems (.net micro framework) where for a given usage pattern the GC was perfectly predictable, as it should be.

What do you mean?

Assuming you use a set of slabs of fixed size objects and keep free objects in a linked list, both malloc and free are trivial O(1) operations.

Destructors with cascading deletions can take time bounded only by memory allocation, but you can solve that for instance by destroying them on a separate thread, or having a linked list of objects to be destroyed and destroying a constant number/memory size of them on each allocation.

Re: Functional languages should be so much better at mutation than they are

#98

Post by devit »

kaba0 wrote: post #89
devit wrote: post #56

Earlier quoted context omitted.

You can, but it turns out that, as one may intuitively expect, a GC is never needed unless implementing a VM for a GC-based language or an API that required GC like fd passing on unix domain sockets, and those generally want an ad-hoc GC instead tailored to whatever you are implementing. Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential an…

> Since it's not needed and it's massively worse than reference counting Lol, what? Maybe don’t go asserting stuff you clearly know little about. Reference counting is a fine tradeoff for manual memory-managed languages, but it is absolutely smoked out of the water by a tracing GC on most counts. It’s almost like JVM, V8, etc engineers know a thing about the topic and don’t have RC for a good reason. Tracing GC doesn…

That's because, unlike Rust, those languages with RC would have a lot of unnecessarily refcounted objects because they don't have value objects, do a whole lot of useless reference count updates because they don't have borrowing and always have to use atomics because they can't ensure that some objects are not shared between threads (and also would need a cycle collector in addition to the reference counting).

If you use reference counting properly in a well-designed language then it's obviously better than GC since it's rarely used, fast, simple, local and needs no arbitrary heuristics.

The destructor cascades are only a problem for latency and potential stack overflow and can be solved by having custom destructors for recursive structures that queue nodes for destruction, or using arena allocators if applicable.

Re: Functional languages should be so much better at mutation than they are

#99

Post by tome »

IshKebab wrote: post #91
tome wrote: post #83

Earlier quoted context omitted.

> (Also, it has exceptions which are a bad language feature, and typed throws which are a worse one.) Can you elaborate? You can't stop people simulating exceptions with sum types, and if you have exceptions, why wouldn't you want them to be typed?

Sum types aren't a simulation of exceptions.

Can you elaborate?

Re: Functional languages should be so much better at mutation than they are

#100

Post by Iceland_jack »

bmacho wrote: post #95
ufo wrote: post #38

Earlier quoted context omitted.

One thing that many people miss is that Haskell's monadic style is a direct consequence of lazy evaluation. It all started because they thought lazyness was nice, and wanted to make a language that brought that front and center. But then they found out that they had to come up with a new way to do side-effects, because traditional side-effects don't work when the order of evaluation is unpredictable.

> One thing that many people miss is that Haskell's monadic style is a direct consequence of lazy evaluation. It all started because they thought lazyness was nice, and wanted to make a language that brought that front and center. But then they found out that they had to come up with a new way to do side-effects, because traditional side-effects don't work when the order of evaluation is unpredictable. But this is no…

Monads don't have anything to do with laziness but historically the need for them arose because of laziness. It's the first thing explained in the introduction of Tackling the Awkward Squad:

"Call-by-need (or lazy) languages, such as Haskell, wear a hair shirt because their evaluation order is deliberately unspecified. Suppose that we were to extend Haskell by adding side-effecting “functions” such as printChar. Now consider this list

  xs = [printChar 'a', printChar 'b']
(The square brackets and commas denote a list in Haskell.) What on earth might this mean? In SML, evaluating this binding would print 'a' followed by 'b'. But in Haskell, the calls to printChar will only be executed if the elements of the list are evaluated. For example, if the only use of xs is in the call (length xs), then nothing at all will be printed, because length does not touch the elements of the list.

The bottom line is that laziness and side effects are, from a practical point of view, incompatible. If you want to use a lazy language, it pretty much has to be a purely functional language; if you want to use side effects, you had better use a strict language.

For a long time this situation was rather embarrassing for the lazy community: even the input/output story for purely-functional languages was weak and unconvincing, let alone error recovery, concurrency, etc. Over the last few years, a surprising solution has emerged: the monad. I say “surprising” because anything with as exotic a name as “monad” — derived from category theory, one of the most abstract branches of mathematics — is unlikely to be very useful to red-blooded programmers. But one of the joys of functional programming is the way in which apparently-exotic theory can have a direct and practical application, and the monadic story is a good example. Using monads we have found how to structure programs that perform input/output so that we can, in effect, do imperative programming where that is what we want, and only where we want. Indeed, the IO monad is the unifying theme of these notes."

https://www.microsoft.com/en-us/research/wp-content/uploads/...

Post reply on HN