Jonathan, I just want you to know that what you're doing is very much needed. Keep on pushing! I'm seriously excited to get to mess with jai. Thanks again for undertaking this tremendous task. Sincerely, Game programmers everywhere
I was taught that internal fragmentation is when you have... say a struct with a bool, an int, and another bool. If you organize the data like that, you're going to waste the 3 bytes of alignment between the bool & the int, and then an additional 3 bytes after the last bool so the next object is also on an alignment (assuming bool is 1 byte, and ints are on 4 byte boundaries). This is an annoying part of C/C++ (for me), that you have to list your data in a specific order so that the memory is better aligned, when the data that those bits refer to would make more sense written in a different order logically. You would waste only 2 bytes if the bools were together, assuming 4 byte boundaries. External fragmentation is actually what you described as internal, where the allocator would like to give a block out (generally after freeing one) but can't because the size of that block is too small for most requests.
I wouldn't call allocatable memory at the end of the heap "fragmentation," either internal or external. That's where you want your free space to be. Fragmentation, either internal or external, is free space scattered among your allocated space. Internal fragmentation is the space that gets skipped or overallocated to align blocks and blocksizes to fullword or doubleword boundaries (or possibly larger powers of 2). On today's systems with large memories, you really shouldn't worry too much about internal fragmentation. It really doesn't take up much space and it's there to make the system run faster (by maintaining favorable memory alignments and by making blocks have sizes that are easier to reuse, and by not having to keep track of "crumbs"--free space that is too small to be useful.) External fragmentation is free space between allocated blocks, (not at the end of all the allocated blocks, which is where you want your free space to be in one large block.) External fragmentation is a problem if the blocks are too small to be easily reused, also, it ruins locality of reference. It's not such a reallocation problem in a fixed size pool, but it's still considered fragmentation. (There is also something called data fragmentation, where the data is cut up into chunks ("extents") to reuse some of the smaller free space fragments when there isn't a single large piece big enough. We see this in file system allocators, not internal memory.)
I think that the ambiguous overload is perhaps needlessly aggressive in your example. For instance, I could have some functions: debug_print(x : int) { print("Debug: Int % ", x); } debug_print(x : string) { print("Debug: string % ", x); } debug_print(x : $T) { print("Debug: type % ", T.Type_Info); } and I don't think that this kind of ambiguity is really a problem. Do you think I am being naive and that "most specific type" style polymorphism rules are a source of bugs?
+Jay Fraser In this case I felt it was better to be very unambiguous. The thing is, with normal overloading, there is some idea of the distance between two types, that is used to resolve overloads due to specificity. (u8 is closer to u32 than u64, etc). Once your type is just $T, and then maybe the #modify does some stuff about the type, the compiler has no visibility into how near or far $T is from u32. But at some point these are just details that can be changed later if it becomes clear what the right answer is.
+Jay Fraser - I feel like this should be allowed but maybe only with some keyword. For example: debug_print :: #weak_overload (x : $T) { ... } This would signify that the programmer is aware that this version of the function might go unused. It would also be handy to be able to quickly exclude types from polymorphic function overloads. Like so: debug_print :: (x : $T/(#not(string) & #not(int))) { ... } but preferrably with much cleaner syntax.
Fellow programmers, I am new to all of this and have only taken OOP...However i desire your opinions, what is a decent pc build for game development? I am looking at a 2D environment programming in C++ with Direct X 12 (For learning and experiance). any opinions? I cant wait to start understanding more of this!
Any PC with a dedicated GPU should be good for 2D development. For DirectX 12 you'll be forced to have Windows 10 running though, so you might wanna use OpenGL or Vulkan instead! :)
How is an empty bucket different from internal fragmentation when it comes to the cache? Surely an empty bucket pollutes the cache just as much as fragmentation in an array.
+DelusionalLogic Next time you create something, you put it in the first empty bucket. So empty buckets should be scarce. It's not the same as fragmentation because fragmentation is what happens when you are not able to usefully employ some memory. In this case you know you always will be able to, because everything is the same size.
+Jonathan Blow I know this is not the topic of the presentation, but you present a bucket list as an alternative to a dynamic array. Given that your objects are of a single type a dynamic array and a bucket list should exhibit similar cache pollution. I guess my main point is that a bucket list is really a tradeoff of insertion speed to iteration speed. You can insert faster, since you don't have to search as many slots for an empty one, and you can allocate a new set of slots faster. But you are going to have to follow some pointers to to iterate through it all. For a dynamic array you have to copy the whole array for allocation, but you don't have to follow any pointers to iterate through it. This turned into a ramble instead of a reply I guess. my initial question was unclear, and I wanted to present my point.
DelusionalLogic The point of the bucket array is that I don't have to reallocate and copy to grow the array, and if I grow the array then entities (or whatever) don't change their positions in memory, so pointers held by anyone else in the system remain valid. This latter point is super-important ... you introduce massive amounts of complexity into your system if you potentially invalidate all pointers any time you want to create an entity, and you introduce a bunch of complexity (and slow down everything) if you require people to use "smart pointers" that update when your array resizes. Sure, you have to follow some pointers to get to each bucket, but provided the buckets are reasonably big, you can prefetch the reads on those pointers while processing the previous bucket. The alternative, the way we did it in The Witness and Braid, we used a flat dynamic array, but it was an array of pointers to the actual entities, whose memory was elsewhere. Then you can resize the array and the entities don't move, but then you're dereferencing a pointer on every single entity visit, which is way worse. (Maybe not as bad as you would think because we try to allocate the entities sequentially in memory, but the Bucket_Array I have shown here is better than what we used in Braid and The Witness in every way.)
+Jonathan Blow Invalidating pointers was something I didn't think of, but a very apt point. I've never run into that problem, but I also don't make games, it's fun to hear a new perspective. I guess I can add bucket lists to my toolbox of datastructures.
You should always consider cache size. While processors have become exponentially fast (until 2005) memory hasn't had that much of a blessing. That's why a bucket of (same) things which are unordered, but in the same space will - generally - perform better.
Nice demo, although I would still like if there were member functions. Anyway, it would be nice to be able to explicitly call the make_iterator functions too, so you could do something like, for make_iterator_reverse(array) ... or for make_iterator_no_killed(actors) ...
+xMyran Member functions are probably not going to happen. I don't see the point, they just make the language worse. As for making specific iterators, as discussed in the Q&A, you can already do that.
+Ihrbekommtmeinen Richtigennamennicht And every time someone posts this, I get mad at them for not bothering to really think about the problem before bugging me. There is nothing magic about typing entities. in an IDE and then seeing "add" to insert after. You could also type entities (and some other key) and see "add" and when you pick that, it inserts the name of the procedure plus a ( before the word entities. None of this matters, it is all trivial.
Calling a function each iteration could limit how fast you can iterate. Have you thought about having a function that iterates forward N items at a time, returning those items in an array?
+panic Is there any reason that building an array should be faster than calling a potentially inlined function multiple times? It seems to me that either you're returning an array that naturally underlies the iterator, in which case the code in the iterator is relatively straightforward, or you have to allocate/copy memory in order to return the array from the iterator, in which case the allocation and copy overhead will outweigh any potential function call overhead. There are probably some cases where it's better, but I doubt it would be common enough to make it look like normal iteration: something strange is happening, and it should probably be visible.
+Caleb Jones You don't have to "build an array": the idea is you'd return a pointer and length to some section of your internal data structure. Check out fast enumeration in Objective-C for an example of how this could work.
Will there be member functions in this language or is there a reason for not having them? I ask this because most procedures so far have been written with the C++ style of passing the object by reference and it seems useful for standard classes like arrays/queues/tables to use member functions instead. Since this is related to OOP, I'm not sure what the direction is on this feature. Edit: Well never mind, already answered. They do make programming easier since an IDE can autocomplete for a particular class. You'll have to look at documentation instead; but there's probably a better reason for their exclusion.
You mean something like: update := *functionName; update(); ? I think the only advantage member functions have is: using the dot operator and IDE to quickly parse through what functions a class has and knowing that object can be used as an operand. Using a function pointer doesn't really take advantage of this and this solution can be implemented in better ways, like a unique id, and an update function that changes based on that id.
Jonathan, I just want you to know that what you're doing is very much needed. Keep on pushing! I'm seriously excited to get to mess with jai. Thanks again for undertaking this tremendous task.
Sincerely,
Game programmers everywhere
I really hope jai gets released this year. Every week without jai hurts my brain.
how's your brain holding up? :)
this year for sure... beta
lol it's now 2020 how's your brain doing bud
Ouch
Oh no it's March 2021.
I was taught that internal fragmentation is when you have... say a struct with a bool, an int, and another bool. If you organize the data like that, you're going to waste the 3 bytes of alignment between the bool & the int, and then an additional 3 bytes after the last bool so the next object is also on an alignment (assuming bool is 1 byte, and ints are on 4 byte boundaries). This is an annoying part of C/C++ (for me), that you have to list your data in a specific order so that the memory is better aligned, when the data that those bits refer to would make more sense written in a different order logically. You would waste only 2 bytes if the bools were together, assuming 4 byte boundaries.
External fragmentation is actually what you described as internal, where the allocator would like to give a block out (generally after freeing one) but can't because the size of that block is too small for most requests.
I wouldn't call allocatable memory at the end of the heap "fragmentation," either internal or external. That's where you want your free space to be. Fragmentation, either internal or external, is free space scattered among your allocated space.
Internal fragmentation is the space that gets skipped or overallocated to align blocks and blocksizes to fullword or doubleword boundaries (or possibly larger powers of 2). On today's systems with large memories, you really shouldn't worry too much about internal fragmentation. It really doesn't take up much space and it's there to make the system run faster (by maintaining favorable memory alignments and by making blocks have sizes that are easier to reuse, and by not having to keep track of "crumbs"--free space that is too small to be useful.)
External fragmentation is free space between allocated blocks, (not at the end of all the allocated blocks, which is where you want your free space to be in one large block.) External fragmentation is a problem if the blocks are too small to be easily reused, also, it ruins locality of reference. It's not such a reallocation problem in a fixed size pool, but it's still considered fragmentation.
(There is also something called data fragmentation, where the data is cut up into chunks ("extents") to reuse some of the smaller free space fragments when there isn't a single large piece big enough. We see this in file system allocators, not internal memory.)
I think that the ambiguous overload is perhaps needlessly aggressive in your example. For instance, I could have some functions:
debug_print(x : int) { print("Debug: Int %
", x); }
debug_print(x : string) { print("Debug: string %
", x); }
debug_print(x : $T) { print("Debug: type %
", T.Type_Info); }
and I don't think that this kind of ambiguity is really a problem. Do you think I am being naive and that "most specific type" style polymorphism rules are a source of bugs?
+Jay Fraser In this case I felt it was better to be very unambiguous. The thing is, with normal overloading, there is some idea of the distance between two types, that is used to resolve overloads due to specificity. (u8 is closer to u32 than u64, etc). Once your type is just $T, and then maybe the #modify does some stuff about the type, the compiler has no visibility into how near or far $T is from u32. But at some point these are just details that can be changed later if it becomes clear what the right answer is.
+Jay Fraser - I feel like this should be allowed but maybe only with some keyword. For example:
debug_print :: #weak_overload (x : $T) { ... }
This would signify that the programmer is aware that this version of the function might go unused.
It would also be handy to be able to quickly exclude types from polymorphic function overloads. Like so:
debug_print :: (x : $T/(#not(string) & #not(int))) { ... }
but preferrably with much cleaner syntax.
Fellow programmers, I am new to all of this and have only taken OOP...However i desire your opinions, what is a decent pc build for game development? I am looking at a 2D environment programming in C++ with Direct X 12 (For learning and experiance). any opinions? I cant wait to start understanding more of this!
Any PC with a dedicated GPU should be good for 2D development.
For DirectX 12 you'll be forced to have Windows 10 running though, so you might wanna use OpenGL or Vulkan instead! :)
Excellent.
How is an empty bucket different from internal fragmentation when it comes to the cache? Surely an empty bucket pollutes the cache just as much as fragmentation in an array.
+DelusionalLogic Next time you create something, you put it in the first empty bucket. So empty buckets should be scarce. It's not the same as fragmentation because fragmentation is what happens when you are not able to usefully employ some memory. In this case you know you always will be able to, because everything is the same size.
+Jonathan Blow I know this is not the topic of the presentation, but you present a bucket list as an alternative to a dynamic array. Given that your objects are of a single type a dynamic array and a bucket list should exhibit similar cache pollution.
I guess my main point is that a bucket list is really a tradeoff of insertion speed to iteration speed. You can insert faster, since you don't have to search as many slots for an empty one, and you can allocate a new set of slots faster. But you are going to have to follow some pointers to to iterate through it all. For a dynamic array you have to copy the whole array for allocation, but you don't have to follow any pointers to iterate through it.
This turned into a ramble instead of a reply I guess. my initial question was unclear, and I wanted to present my point.
DelusionalLogic The point of the bucket array is that I don't have to reallocate and copy to grow the array, and if I grow the array then entities (or whatever) don't change their positions in memory, so pointers held by anyone else in the system remain valid. This latter point is super-important ... you introduce massive amounts of complexity into your system if you potentially invalidate all pointers any time you want to create an entity, and you introduce a bunch of complexity (and slow down everything) if you require people to use "smart pointers" that update when your array resizes.
Sure, you have to follow some pointers to get to each bucket, but provided the buckets are reasonably big, you can prefetch the reads on those pointers while processing the previous bucket.
The alternative, the way we did it in The Witness and Braid, we used a flat dynamic array, but it was an array of pointers to the actual entities, whose memory was elsewhere. Then you can resize the array and the entities don't move, but then you're dereferencing a pointer on every single entity visit, which is way worse. (Maybe not as bad as you would think because we try to allocate the entities sequentially in memory, but the Bucket_Array I have shown here is better than what we used in Braid and The Witness in every way.)
+Jonathan Blow Invalidating pointers was something I didn't think of, but a very apt point. I've never run into that problem, but I also don't make games, it's fun to hear a new perspective. I guess I can add bucket lists to my toolbox of datastructures.
You should always consider cache size. While processors have become exponentially fast (until 2005) memory hasn't had that much of a blessing. That's why a bucket of (same) things which are unordered, but in the same space will - generally - perform better.
Nice demo, although I would still like if there were member functions. Anyway, it would be nice to be able to explicitly call the make_iterator functions too, so you could do something like,
for make_iterator_reverse(array) ...
or
for make_iterator_no_killed(actors) ...
+xMyran Member functions are probably not going to happen. I don't see the point, they just make the language worse. As for making specific iterators, as discussed in the Q&A, you can already do that.
+Ihrbekommtmeinen Richtigennamennicht And every time someone posts this, I get mad at them for not bothering to really think about the problem before bugging me. There is nothing magic about typing entities. in an IDE and then seeing "add" to insert after. You could also type entities (and some other key) and see "add" and when you pick that, it inserts the name of the procedure plus a ( before the word entities. None of this matters, it is all trivial.
why do you need $T/Entity if you can just make it a regular overload like foo :: (Entity) i see the use case for struct with parameters
Calling a function each iteration could limit how fast you can iterate. Have you thought about having a function that iterates forward N items at a time, returning those items in an array?
+panic Is there any reason that building an array should be faster than calling a potentially inlined function multiple times? It seems to me that either you're returning an array that naturally underlies the iterator, in which case the code in the iterator is relatively straightforward, or you have to allocate/copy memory in order to return the array from the iterator, in which case the allocation and copy overhead will outweigh any potential function call overhead. There are probably some cases where it's better, but I doubt it would be common enough to make it look like normal iteration: something strange is happening, and it should probably be visible.
+Caleb Jones You don't have to "build an array": the idea is you'd return a pointer and length to some section of your internal data structure. Check out fast enumeration in Objective-C for an example of how this could work.
+panic iterator_next can easily be inlined (and is in the example I showed).
I came here for rain world
Ok bye
What about inline assembly?
Jon's already said that inline assembly was a thing he wanted, he just hasn't shown it (probably not had a need for it yet).
Will there be member functions in this language or is there a reason for not having them? I ask this because most procedures so far have been written with the C++ style of passing the object by reference and it seems useful for standard classes like arrays/queues/tables to use member functions instead. Since this is related to OOP, I'm not sure what the direction is on this feature.
Edit: Well never mind, already answered. They do make programming easier since an IDE can autocomplete for a particular class. You'll have to look at documentation instead; but there's probably a better reason for their exclusion.
You mean something like:
update := *functionName;
update(); ?
I think the only advantage member functions have is: using the dot operator and IDE to quickly parse through what functions a class has and knowing that object can be used as an operand. Using a function pointer doesn't really take advantage of this and this solution can be implemented in better ways, like a unique id, and an update function that changes based on that id.