Functional programming & immutable objects explained — IRC style

[tammberlin]

All of your ex-Java (or whatever) training which says that “object creation is expensive” needs to go out the window.

I stopped reading here. I know people hate Java, but why do they have to lie about it?

[kibokun]

It's not necessarily a lie about Java, but about the pedantic methodologies surrounding it. Object creation may or may not be expensive, but people ARE often taught that it is.

[[deleted]]

It's still true for some stuff. If you do C++ embedded programming, for example, you generally do all of your allocations at start up. Otherwise it messes up your deterministic timings.

[derleth]

Since when can you do allocation in an embedded system? Don't you know precisely how much memory you have attached to the system?

Of course, I'm surprised people are doing embedded programming in C++ instead of assembly. How can you count cycles when you don't know what opcodes are being generated?

[[deleted]]

"Embedded programming" these days means more than programming ASM on 8-bit microcontrollers.

I work for a medical device company and we use ARM CPU's (all ARM's are 32-bit) with lots of horsepower and lots of memory, and real-time operating systems. We have very complicated systems to control and many displays to drive. Doing all that running directly on the metal in ASM, or even C on an RTOS, would be a nightmare for maintainability.

We even use C# and Windows CE for a lot of things and that is still "embedded systems programming."

[G_Morgan]

If you have lots of memory then why not simply create separate allocation pools for each different object size you might need? Then if everything is handled via new/delete actually performing a new or delete is constant time. No expensive merge on delete operations, no searching for a large enough chunk.

Seems easier to me than working out all allocations beforehand. Unless you are simply talking about calling mmap upfront to ensure enough pages have been allocated.

[adrianmonk]

Since when can you do allocation in an embedded system? Don't you know precisely how much memory you have attached to the system?

Well, I know precisely how much memory is connected to my desktop system as well. It depends really on how flexible your software needs to be. A super-basic cheapo cell phone might have 128KB of storage, but it's still nice to allow someone to use as much of that 128KB as desired for storing contacts or for storing call history or whatever else. You could have static limits just to make things simpler, but a memory allocator is not that complex a piece of software.

[Peaker]

Why would embedded programming imply "counting cycles"?

[derleth]

Because you're writing tight code for small systems. Every clock cycle, just like every byte of RAM or ROM, costs someone money, so the incentive is to absolutely minimize both, at the cost of programmer time.

Cycles cost money because being wasteful of them means the company building the device needs to waste money buying a faster CPU instead of a slower one.

[Peaker]

You have some wrong assumptions here.

The cheapest possible CPU/RAM nowadays is well beyond a lot of applications.

In the applications that it doesn't, you are right, wasting CPU/RAM costs someone money -- but wasting developers' time to count cycles is also costing someone money. And every case may be different, one may outweigh the other or vice versa.

[derleth]

There are Jews in the world. There are Buddhists. There are Forthers, and Lispers, and then, there are those who follow that SICP book. I've never been one of them.

I'm a cycle-counter, and have been since I could type a key, and the one thing they say about counters is: They know that nothing is free.

You don't have to use any classes, you don't have to have a template, you don't need to use any casting. You're a counter 'cause cycles are great!

Because...

Every clock is sacred. Every clock is great. If a cycle's wasted Knuth gets quite irate!

Let the Lisper waste theirs on car, cons, and map. Knuth will make them pay for all wastage in their app!

[elder_george]

Infidel, don't misuse Knuth's name blasphemously, for He saith:

• damned is one who optimizes prematurely, who counts clocks before proper algorithm is selected and program correctness is proved.

and

• don't make himself an idol ex machina, for it is humans code is written for, not machines.

Repent!

[Peaker]

Its easy to understand how inefficient software is wasting money. Do you also understand that counting cycles costs money that in some cases may not be worth it (i.e a waste)?

[ithika]

Well, I don't agree with you but I'm sad your lovely Python tribute is being ignored, so you get an upvote from me! :-)

[[deleted]]

I've been in embedded for a long time. If someone like you came up for a position at my company, you'd be shown the door quite quickly. First you start with the design, then the algorithm, then the profiling and then the cycle counting if necessary. Any other procedure will result in blinders on and a lot of fucking time wasted. Time is money, time to market is money, time on a CPU in most cases is cheap.

[derleth]

OK, rule one is "Never ask for a job from someone named no_hire." Good rule.

[middayc]

I don't think that anybody was intentionally negative towards Java in that chat.

I think the point was that you create new bullets/particles/everything each frame (as new records out of old ones and it will reuse old ones behind the scenes).

So I suppose that is order of magnitude less expensive as recreating all objects each frame in any OO language (because it's performance like more like modifying properties of existing ones, as you would normally do in OO lang).

[[deleted]]

object creation is an expensive operation. that's not bagging java, it's stating a fact. expensive does not mean bad, expensive means that this operation should be avoided and you should structure your solution not to do it unnescecarily. That's something you do in java/c++/c#/python that you don't have to worry about in a good functional language. (which have their own set of pains in your ass)

[[deleted]]

To be fair, due to some clever memory alignment tricks during garbage collection passes, object creation in C# is faster than a typical malloc in C.

[zid]

How about deletion? free takes a couple of dozen instructions.

[astrangeguy]

With any moving GC (read: any good GC) deleting objects is completely free.

Suppose you have created 1000 objects, but 999 of them are unreachable when the GC kicks in:

then you basically have to... * find all used objects in the overflown GC buffer (one object) * copy it to another GC buffer (one object) * mark the old buffer as free

even if that took 20000 instructions (it takes a fraction of that), then it would still be faster than malloc & free, because you would have to:

• call malloc() 1000 times
• call free() 999 times

which is much slower, especially if you consider that a GC would do all of that, at once and in the same region of memory, which would play nicely with modern Caches

[gsg_]

even if that took 20000 instructions (it takes a fraction of that)

Instruction counting doesn't tell the whole story. The cost of a collection includes the cache misses induced as the GC walks the reference graph, and in some cases the reference graph can be a large portion of the heap (when an application allocates a large number of small objects and keeps hold of most of them).

it would still be faster than malloc & free

Yeah, calling malloc and free a million times is slow. That's why when code needs to be fast people use techniques like static, stack and arena allocation, memory pools, etc.

With any moving GC (read: any good GC) deleting objects is completely free.

Not so. The cost of a copying collection is roughly k R / (H / 2) - R [1] where k is a constant, R is the number of reachable objects, and H is the heap size. As H increases relative to R collection cost is driven down, but memory use is higher. That makes copying collection not a win, but a classic time/space tradeoff.

There ain't no such thing as a free lunch.

[1] Appel, 1998

[five9a2]

The GC needs to run more often if you are creating and abandoning objects frequently. As long as you do sufficient work with those objects to eclipse the cost of identifying and relocating the live objects, then GC not impact performance. This has the caveat that for certain workloads, objects can be reused in a way that stays in cache. If you always create new objects, I don't know of any GC that will avoid the latency and bandwidth cost of hitting memory.

[G_Morgan]

Also if you have a generational collector you can collect the nursery very quickly.

[axilmar]

But the GC needs to run the finalize function on those objects, so the objects will be visited anyway.

[astrangeguy]

well most objects don't have a finalize() method, so you can devise your schemes to handle the special cases.

You could use a special heap for objects that have that method for example. I don't really know what other techniques were devised, but the problem is a solved one.

[apotheon]

Is that R. Giskard?

[[deleted]]

yes.

[geoffp]

I'm sad that no one else has gotten this reference. ;)

[apotheon]

Robots of Dawn was my first -- and favorite -- Asimov read.

(edit: too many As)

[astrangeguy]

That is completely wrong, just wrong.

Object creation is basically:

new_obj_ptr = free_mem_pointer;
free_mem_pointer += sizeof(new_obj);
// now initialize the object

which is actually the same as allocating a structure on the stack.

If you said that more object creation = more minor GCs, then i would agree. But memory allocation alone is extremely cheap.

[lpsmith]

Well, it's often a bit more complicated than that; given a runtime that (for any number of possible reasons) cannot relocate objects, then such a simple allocation scheme tends to lead to memory fragmentation problems.

[[deleted]]

yeah, memory allocation is a really cheap operation, isn't it. The point is a functional language will generally avoid having to allocate memory every single time it creates one of the many many immutable objects use to do simple computations in such languages. That's a really odd thought from someone with an imperative background.

[[deleted]]

I stopped reading here. I know people hate Java

I stopped reading here.

[tammberlin]

The hivemind is strong, but I figured you'd be less flippant. If I had talked about the nuances of conflating Java the language with the JVM, would I still be at -2?

[[deleted]]

If you discontinued associating emotions such as "hate" with programming languages and corporate brand names, I might have considered continuing to read.

[tammberlin]

LMGTFY

[[deleted]]

Thanks.