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

Show HN: Micro-mitten – Research language with compile-time memory management

github.com

Post reply on HN
Print view View original

51–60 of 68 posts

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#51

Post by littlestymaar »

scott_s wrote: post #12
flohofwoe wrote: post #2

> This means that it maintains the ability to insert freeing code at appropriate program points, without putting restrictions on how you write your code. How does the approach in mitten compare to Automatic Reference Counting in Objective-C (and I think Swift too)? From my experience, ARC can still add a surprising amount of memory management overhead to a program and needs a lot of hand-holding to keep that overhead…

From the ASAP dissertation ( https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf ): > Reference counting, like asap, is a safe, synchronous memory management strategy. However, rc approximates waste by unreachability which is less timely than asap’s approximation by Access. I think a more careful reading of the work is required to distinguish the precise meanings of "unreachability" and "access" in this context.

As I understand it:

- unreachability means there's no live reference to that object. - access means somebody is going to use this object again. If you have a live reference but won't ever use it again it's a kind of leak (that's how GCed languages can leak memory without any manual management).

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#52

Post by catblast »

eklavya wrote: post #3
flohofwoe wrote: post #2

> This means that it maintains the ability to insert freeing code at appropriate program points, without putting restrictions on how you write your code. How does the approach in mitten compare to Automatic Reference Counting in Objective-C (and I think Swift too)? From my experience, ARC can still add a surprising amount of memory management overhead to a program and needs a lot of hand-holding to keep that overhead…

From what I understood, it’s not reference counting but trying to determine at compile time when to drop using data flow analysis to come up with an approximation of the liveness. I had a thought sometimes back, can compilers do a profile run to get information about the liveness of objects it couldn’t determine statically by dumping gc info?

> get information about the liveness of objects it couldn’t determine statically by dumping gc info?

Well it may be possible to optimize via profiling (this is what PGO is), but this of course wouldn’t be a static analysis, so it would just allow some optimizations on dynamic access.

In theory you could use profiling as part of the implementation of a theorem prover, but I haven’t seen any examples where that is more effective then the conventional methods of data flow analysis. And in this case, it would still be static analysis.

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#53

Post by philipkglass »

_bxg1 wrote: post #46
wtetzner wrote: post #39

Earlier quoted context omitted.

Maybe there could be a compiler flag. You let any program compile normally, but if you enable the flag, it only allows programs to compile if the maximum memory usage can be computed, and if there are under the limit you specify. That means the language isn't always crippled, but you can get compiler enforcement for certain embedded programs.

It would effectively become a stack-only language (heap allocations' sizes would always have to be known at compile time, just like on the stack). I could see that serving an interesting special subset of use-cases, but I was under the impression we were talking about a general programming language, which that would not be.

Fortran didn't have dynamic memory allocation until Fortran 90. If you wanted to run a problem larger than the original code's author had anticipated, you needed to recompile the source with larger values. This could indeed be an annoying restriction. But you might be surprised how much software was successfully written in Fortran.

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#54

Post by mcguire »

flohofwoe wrote: post #2

> This means that it maintains the ability to insert freeing code at appropriate program points, without putting restrictions on how you write your code. How does the approach in mitten compare to Automatic Reference Counting in Objective-C (and I think Swift too)? From my experience, ARC can still add a surprising amount of memory management overhead to a program and needs a lot of hand-holding to keep that overhead…

"How does the approach in mitten compare to Automatic Reference Counting in Objective-C (and I think Swift too)? From my experience, ARC can still add a surprising amount of memory management overhead to a program and needs a lot of hand-holding to keep that overhead down to an acceptable level (e.g. low single-digit percentage of overall execution time in programs that talk to Obj-C APIs a lot). I would be surprised if a "traditional GC" can do any worse in that regard (maybe reference counting smears the overhead over a wider area, e.g. no obvious spikes, but instead "death by a thousand cuts")."

The reference counts have to be incremented when a new reference is made and decremented when one is deleted; freeing the memory when the count goes to zero. (This activity is cache- and atomicity-unfriendly (in the presence of threads).) A sufficiently smart compiler can omit many if not most of the count activity, but this kind of static analysis promises to remove all of it.

Further, reference counting has difficulty with circular references as the counts never go to zero. This should also be able to handle that.

Both this and reference counting are likely victims of the "death by a thousand cuts" you mention, as well as "drop the last pointer to a large structure and wait for a long time while the pieces are deleted"---the reference counting equivalent of a stop-the-world-and-trace garbage collection.

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#55

Post by pjmlp »

api wrote: post #34

If unrestrictive compile time GC is possible, couldn't this be retrofitted into JITs for JavaScript, Java, .NET, WASM, etc.? Isn't this just another way of implementing GC?

JITs already do this kind of thing, it is called escape analysis, it is just quite hard to get right.

Also many GC based languages are adding some form of linear types, so that you can still enjoy the productivity of having a GC around, while being able to get hold of these kind of tools.

https://github.com/apple/swift/blob/master/docs/OwnershipMan...

https://gitlab.haskell.org/ghc/ghc/-/wikis/linear-types

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#56

Post by TheAsprngHacker »

fluffything wrote: post #48
syockit wrote: post #45

I imagine the compile would be magnitudes slower than Rust or C++, and I can't really stomach slow compilers. Yesterday I was hacking on a Qt app and the time taken to rebuild after a slight change to the header is distressing (more than 5 seconds, which can afford a full rebuild on a typical C program). I'm kind of surprised that the quick sort example took only around twice to thrice as long to compile compared to…

> I imagine No need to image, the thesis mentioned in the README provides compile-time results. From no noticeable overhead to 2x larger compile-times than Rust. Quite reasonable if you take into account that one is one person's university thesis, and the other is a project with 100s of active developers, 100s of open PRs, etc.

To my understanding skimming the paper, the analysis must compute "call contexts" of functions, which use information from call sites. I wonder if this will impede incremental compilation and modularity. As programs get bigger, perhaps this approach may not scale.

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#58

Post by zokier »

_bxg1 wrote: post #46
wtetzner wrote: post #39

Earlier quoted context omitted.

Maybe there could be a compiler flag. You let any program compile normally, but if you enable the flag, it only allows programs to compile if the maximum memory usage can be computed, and if there are under the limit you specify. That means the language isn't always crippled, but you can get compiler enforcement for certain embedded programs.

It would effectively become a stack-only language (heap allocations' sizes would always have to be known at compile time, just like on the stack). I could see that serving an interesting special subset of use-cases, but I was under the impression we were talking about a general programming language, which that would not be.

For example MISRA C disallows dynamic memory allocations completely and still pretty complex applications have been written to that spec. Similar guidelines are pretty common in other high reliability or safety critical software specifications. Another example is "JPL Institutional Coding Standard for the C Programming Language", which specifies "Do not use dynamic memory allocation after task initialization"

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#59

Post by Someone »

mcguire wrote: post #54
flohofwoe wrote: post #2

> This means that it maintains the ability to insert freeing code at appropriate program points, without putting restrictions on how you write your code. How does the approach in mitten compare to Automatic Reference Counting in Objective-C (and I think Swift too)? From my experience, ARC can still add a surprising amount of memory management overhead to a program and needs a lot of hand-holding to keep that overhead…

" How does the approach in mitten compare to Automatic Reference Counting in Objective-C (and I think Swift too)? From my experience, ARC can still add a surprising amount of memory management overhead to a program and needs a lot of hand-holding to keep that overhead down to an acceptable level (e.g. low single-digit percentage of overall execution time in programs that talk to Obj-C APIs a lot). I would be surprise…

”This activity is cache- and atomicity-unfriendly (in the presence of threads).“

Indeed it is. https://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf states reference counting takes 42% of execution time in client programs and 15% in server programs.

Luckily, they also present amore cache-friendly variation on reference counting that halves that overhead.

They modified the Swift compiler, so I think there’s a decent chance we’ll see this added to Swift.

Swift also, I think, is somewhat designed around the inefficiency of reference counting by promoting the use of structs for small objects (structs in Swift are value objects and not reference-counted in the language).

Re: Show HN: Micro-mitten – Research language with compile-time memory management

#60

Post by megameter »

flohofwoe wrote: post #23
Someone wrote: post #20

Earlier quoted context omitted.

Isn’t that just a variant on organizing your globals well to make using lots of globals manageable? That’s what historically was done in languages such as FORTRAN and COBOL (both of which had compile-time memory management, but managed to do that by completely dropping memory allocation at runtime) And yes, that meant dropping all dynamic memory allocation, too. If your wanted to run your FORTRAN program on a larger…

Most likely! I never wrote FORTRAN or COBOL, but instead was too heavily influenced by the OOP hype of the 90s, and I think this hype still heavily lingers on even in the current "post-OOP" world. It feels like memory management is still heavily stuck in the "every small thing in a program needs its own lifetime" mindset. Remembering how I did "memory management" in my early 8-bit assembler programs (e.g. not at all,…

I reached a similar conclusion. Dynamic memory is seductive for the task of indefinite scaling, but a practical system always encounters bottlenecks that aren't along the memory management axis, and in the meantime your code is much harder to verify.

NB: Historically, game engines have tended towards object pooling at runtime without any dynamic allocations. In that case there is a defined limit to what a scene will accommodate, and the object counts often simply reflect the other performance bottlenecks involved.

GC is still nice, but mostly in the sense of stitching together the most dynamic elements of the system. You don't want to have to trace a ton of stuff, and that also leads in the direction of flattening the data and making it more manual and static as the type system allows.

Post reply on HN