<bytecoder>
seeing as you guys know so much about GCs
<bytecoder>
do you think embedding it into the application will help with the speed issue?
<Smerdyakov>
No.
<Smerdyakov>
I don't see any difference between what you said and statically linking it from a library.
<bytecoder>
I was planning on mapping out every place a dynamically allocated object could possibly be deleted
<bytecoder>
and inserting the appropriate memory-handling code there
<Smerdyakov>
bytecoder, you mean you don't want to use GC at all?
<bytecoder>
I guess
<bytecoder>
I would still have to deal with circular dependencies, though
<Smerdyakov>
You want to use reference counting instead?
<bytecoder>
now that I think about it
<bytecoder>
that does sound a lot like reference counting :/
TeXitoi has quit ["Lost terminal"]
<Smerdyakov>
I encourage you to gather some empirical data before deciding that a standard GC will provide unacceptable performance for your application.
<bytecoder>
my application?
<bytecoder>
actually
<bytecoder>
I have a document about fast garbage collection right here
<Smerdyakov>
I thought that you are concerned with performance of either your compiler or the programs it will generate.
<bytecoder>
still
<Smerdyakov>
Your compiler will not be used to generate all possible programs.
<bytecoder>
well, my goal is to make it as fast/nearly as fast as C
<Smerdyakov>
It would be silly to assume that the class it will be used to generate includes any cases wehre GC is unacceptable.
<bytecoder>
without too much memory usage
<bytecoder>
well
<Smerdyakov>
Oh, that's easy. OCaml and MLton already produce output meeting that criterion.
<bytecoder>
I'm planning on writing the rest of the OS in that language
<bytecoder>
I know
<bytecoder>
except for the memory part
<bytecoder>
I'm just exploring multiple options
<Smerdyakov>
No, including the memory part.
<Smerdyakov>
Just look at some benchmarks.
<bytecoder>
I did
<bytecoder>
but I'll look again
<Smerdyakov>
Negligible difference between MLton and gcc output speed.
<Smerdyakov>
Or do you mean total memory usage is what you want to keep down?
<bytecoder>
what do you mean by "total"
<Smerdyakov>
Forget I said "total."
<bytecoder>
yup
<Smerdyakov>
An OS shouldn't contain much code. Why not use C?
<bytecoder>
well
<bytecoder>
I'm using the linux kernel
<bytecoder>
I mean the applications that run on the OS
<bytecoder>
besides X
<bytecoder>
and command line
<pango>
GCs are also optimized for some memory usage patterns (rate of allocation, average lifetime,...)
<bytecoder>
well, my goal for the language is to automize as much as possible
<Smerdyakov>
bytecoder, why would someone want to use your language instead of ML?
<bytecoder>
similiar to a python-o'caml crossbread
<bytecoder>
heh
<bytecoder>
bread
<bytecoder>
breed
<bytecoder>
it has better data-description facilities
<bytecoder>
I guess is what you'd say
<Smerdyakov>
bytecoder, example?
<bytecoder>
basically, you can fine tune exactly what values are valid for a given type
<Smerdyakov>
There are no widely used, dependently typed languages that I'm aware of, and that's not without reason.
<Smerdyakov>
Type-checking usually requires extra user annotations.
<bytecoder>
the types aren't required
<bytecoder>
they're basically there for error-checking
<bytecoder>
instead of you having to do it manually (like in python), it will be done by the compiler
<Smerdyakov>
So your language is dynamically typed.
<bytecoder>
such that a variable never holds an invalid value
<bytecoder>
I guess you could say that
<bytecoder>
dynamically typed with constraints
<bytecoder>
it also happens to be type-inferred
<bytecoder>
for variables inside routines
<Smerdyakov>
bytecoder, that's an undecidable problem if you have dependent types.
<bytecoder>
the difference between ocaml, in this sense, is that a type can be a combination of other types
<Smerdyakov>
Even just inside routines.
<bytecoder>
hmm?
<Smerdyakov>
It is impossible to write a program that can infer types for all valid uses of variables in the presence of dependent types.
<bytecoder>
example?
<Smerdyakov>
Example: Your language, as I understand it.
<bytecoder>
heh
<bytecoder>
do you have a snippet of code in which that would be true?
<bytecoder>
think about it this way
<Smerdyakov>
This isn't a statement about particular programs.
<bytecoder>
the type system is almost identical to python's
<Smerdyakov>
This is a statement about the entire language.
<Submarine>
in the presence of dependent types, typing is equivalent to some sort of logic
<bytecoder>
except it allows you to constrain a type to a given set of values
<Submarine>
so inferring typing becomes like testing if logic formulas are true
<Smerdyakov>
bytecoder, complete type inference for Python is already impossible.
<Submarine>
which is undecidable
<bytecoder>
I still don't get it
<Smerdyakov>
bytecoder, adding dependent types makes it undecidable for more interesting reasons than that you can assign differently typed values to variables in the branches of an if..else.
<bytecoder>
so?
<bytecoder>
if blah:
<bytecoder>
var = 10
<bytecoder>
else:
<Smerdyakov>
bytecoder, you don't understand what I'm telling you is true or you don't understand why it is true?
<bytecoder>
var = 10.0
<bytecoder>
then the type would be int | float
<pango>
bytecoder: check gcaml
<Smerdyakov>
bytecoder, sure, you can give any variable the type 'anything', but would that really deserve to be called "type inference"?
<bytecoder>
the type inferrence has other uses
<bytecoder>
e.g. for compile-time error checking
<Smerdyakov>
bytecoder, OK, imagine we are using type inference for Python compile-time error checking.
<bytecoder>
ok
<Smerdyakov>
bytecoder, it is impossible to write such a type inferencer which always comes to the correct conclusion on whether the program will try to use a value at the wrong type.
<bytecoder>
yeah
<bytecoder>
and?
<Smerdyakov>
...and you want to do that for an even more complicated type system.
<Smerdyakov>
So something has to give.
<bytecoder>
I was just thinking about that, actually
<bytecoder>
it would, obviously, have to be handled at runtime
<bytecoder>
or you could *eww* give out a warning
<Smerdyakov>
Or you could just use ML, where type inference is decidable.
<bytecoder>
but that would be no fun
<bytecoder>
;)
<bytecoder>
wait a minute...
<bytecoder>
how does ML do it?
<bytecoder>
oh wait
<Smerdyakov>
By designing the typing rules so that it all works out.
<bytecoder>
I see
<bytecoder>
it removes some flexibility
<Submarine>
they restrict stuff
<bytecoder>
meh
<bytecoder>
I think it's worth it
<Submarine>
well, there are some more flexible type systems, like Coq's
<Submarine>
but in Coq, type inference is limited
* Smerdyakov
just ordered Coq'Art from Amazon. ;)
<bytecoder>
I don't get it
<bytecoder>
oh
<bytecoder>
was that a joke?
<Smerdyakov>
Coq is a computer profo assistant that includes a programming language.
<Smerdyakov>
s/profo/proof
<Submarine>
and its type system is more flexible than ML's
<Submarine>
but inferrence is not possible
<Submarine>
because if you can infer types for Coq, you basically can solve most logic problems you can think of
<Submarine>
including deciding whether math theorems are true or false
<Smerdyakov>
The inference problem isn't even well-defined, because Coq doesn
<Smerdyakov>
't have principal types.
<Submarine>
it happens surprisingly fast once you add some features
<Submarine>
Smerdyakov, let's say you can formally define something similar to inference that is undecidable
<bytecoder>
hmm
<bytecoder>
can cyclic dependency checking be implemented in a reference counting system?
<Smerdyakov>
bytecoder, usually such systems call a copying GC ever now and then, if they care about cycles.
<bytecoder>
oh
Submarine has quit ["Leaving"]
<Smerdyakov>
I know you're down on high memory usage, but copying GC tends to be much more efficient than reference counting for the typical ML program.
<Smerdyakov>
(time efficient)
<bytecoder>
how much more memory?
<Smerdyakov>
The simplest copying GC scheme won't use more than twice as much memory as optimal.
<bytecoder>
ouch
<bytecoder>
that's a lot when you're talking about entire environments
<Smerdyakov>
Memory is cheap these days. I don't lose any sleep over it in a desktop or server setting.
<bytecoder>
yes, but more memory != more speed
<Smerdyakov>
It does with a copying GC.
<bytecoder>
more memory usage*
<bytecoder>
not when you're paging like hell
<Smerdyakov>
Yup.
<bytecoder>
meh
<bytecoder>
I still have to figure out how the type system is going to work
<Smerdyakov>
I think you don't understand how the "extra" memory is used.
<pango>
if you need paging it gets worse, because you need a GC that's locality aware
<Smerdyakov>
Semispace copying GCs have two "copies" of the heap.
<bytecoder>
ok
<Smerdyakov>
In the simplest, stop-and-copy versions, only one copy is used at once.
<Smerdyakov>
The live parts of one are copied to the other to perform a GC.
<Smerdyakov>
So, there is no extra paging between GCs.
<bytecoder>
oh
<pango>
but if one copy is too large to fit in memory, if copying shuffles hot and cold memory objects within pages, you have a problem
<Smerdyakov>
If one copy is too large to fit in memory, you also have problems with reference counting.
<bytecoder>
well
<bytecoder>
I could always use reference counting and weak references
<bytecoder>
that depends on how rare cyclical dependencies are
<pango>
I'd like ocaml GC to be more cache aware btw, I don't think it currently is
<Smerdyakov>
bytecoder, you do know that there are many cases (including typical ML programs) where copying GC is significantly faster than reference counting, with enough memory, right?
<bytecoder>
well, I'm not really worried about speed, so much as memory
<Smerdyakov>
OK, as long as you're aware that you're making a trade-off.
<bytecoder>
hopefully, it won't need to be used so much with proper local-variable detection in place
<Smerdyakov>
In the worst case, reference counting can be slower by a factor of about the size of the heap.
<Smerdyakov>
Which can be pretty abysmal.
<bytecoder>
I don't get that
<Smerdyakov>
Every free operation takes cycles with RC.
<Smerdyakov>
Copying GC takes zero cycles to "free" a dead object
<bytecoder>
I was just planning on adding an if statement at the end of routines
<bytecoder>
hmm
<pango>
there's a huge bibliography on the hot GC topic, and lot available for free on the web
<Smerdyakov>
So look at a program that allocates an object and then never uses it again, inside a loop.
<Smerdyakov>
Copying GC will crush RC for such a program.
<bytecoder>
well, the same object could be reused for each iteration
<bytecoder>
no need to allocate/deallocate every time
<Smerdyakov>
It could be, but that's trickier to infer automatically.
<bytecoder>
besides
<bytecoder>
such a usage should be inferrable as local, anyway
<bytecoder>
as long as the variable isn't passed to a routine that saves a reference, it can be local
<Smerdyakov>
Any allocation pattern where most objects die young is going to work better with copying GC than RC.
<bytecoder>
that can be inferred, too
<bytecoder>
well
<Smerdyakov>
This can involve objects stored in global variables and replaced each time some amount of time has past.
<bytecoder>
the object wouldn't need freeing if it was local
<Smerdyakov>
I'm not talking about lexically local variables anymore.
<bytecoder>
ok
<bytecoder>
enum, anyone?
<Smerdyakov>
Just imagine you have a number of threads all adding to a list, and every 100 milliseconds, another thread erases the list.
<pango>
ocaml uses two generations, young generation is managed by mark&sweep, old generation by (incremental) copy
<Smerdyakov>
You're not going to infer "locality" in that example, and it wouldn't be of much use if you did.
<bytecoder>
imaging shooting the programmer who wrote it?
<bytecoder>
that aside
<Smerdyakov>
Or just think of a compiler, analyzing every function in your program.
<Smerdyakov>
There is probably a lot of state needed only during a particular function analysis.
<Smerdyakov>
This state is dead across different function analyses.
<Smerdyakov>
This "locality" is probably not expressed lexically.
<Smerdyakov>
Or, to put it another way, you'd rather not to be forced to write code in a way that expresses lifetimes of dynamically allocated objects.
<Smerdyakov>
Especially in languages like the MLs where dynamic allocation is implicit.
<pango>
my bad, the reverse. Thinking about it, it's more logical
<bytecoder>
I'm basically just planning on having the compiler do whatever a programmer would do manually
<bytecoder>
to an extent, of course
<pango>
so bad ? :)
<bytecoder>
don't feel bad
<bytecoder>
;)
<bytecoder>
hmm
<bytecoder>
speaking of GC, don't you get hiccups everytime it collects?
<pango>
bytecoder: with ocaml, it depends on the size of slices of the incremental mark&sweeping
<Smerdyakov>
Not with a real-time collector, which OCaml doesn't have.
<bytecoder>
ok
<bytecoder>
well, thanks for the advice
<bytecoder>
bye
bytecoder has quit ["Leaving"]
threeve has quit [Connection timed out]
<pango>
I remember seeing a paper on a method similar to what he describes (trying to determine lifetime statically whenever possible, GC when it's not possible), but I don't remember the exact name, nor where I saw it... how irritating
Skal has quit [Remote closed the connection]
<Smerdyakov>
You may be thinking of region-based memory management as implemented in the ML Kit.