4 ms·

I don't have a CS background, so apologies in advance if these are basic questions, but: > For this layout to work though, constructor needs to allocate memory

by scubbo 7y ago

I don't have a CS background, so apologies in advance if these are basic questions, but: > For this layout to work though, constructor needs to allocate memory for the whole object at once. It can’t allocate just enough space for base, and than append derived fields afterwards. But such piece-wise allocation is required if we want a record syntax were we can just specify a value for a base class. 1. Why can the constructor not allocate memory "progressively" for the object as the construction chain descends the class hierarchy? Is it because, in a multi-threaded program, something else might allocate some of the "extended" memory, causing a clash when the constructor attempts to append fields? I assume that an approach of "if the memory that a constructor is trying to append into is already allocated, first move the occupying object to a free memory location, and then continue with allocation" is inefficient because it relies on an "overseer" that can coordinate and resolve these clashes? 1a. Sub-question - why does the memory for an object need to be contiguous? Is this purely an efficiency concern ("read a whole object sequentially" being more efficient than "read an object by reading a bunch of pointers and then reading the locations they point to"), or are there other considerations? I was under the impression that RAM (unlike hard drives) has no (or, negligible) performance penalty to random access - but maybe those intermediate "jumps" add up to a measurable impact? 2. "But such piece-wise allocation is required if we want a record syntax were we can just specify a value for a base class." I don't understand this claim at all. Why is this required? What does it mean to "specify a value for a base class" - is this shorthand for "specify a value for a field of a base class"? Recommendations for further reading are received just as gratefully as direct explanations - I'm sure these concepts are already covered in the literature or a course syllabus, but I have no idea where to start!

firethief 7y ago
If you want to understand this article you'll need to learn a programming language like C. Once you know what the stack, the heap, and records/fields are you'll be able to ask meaningful questions.
- morelisp 7y ago
  It's weird to see a recommendation to learn C when 'scubbo's questions already indicate some knowledge of memory management - far more than you will learn "learning C". The suggestion to "allocate memory progresively" and not-necessarily-contiguously resembles Lisp cons cells, and the questions about how to handle conflicts are the first steps to inventing (and then finding the downsides of) https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding. The second question is also reasonable, "a value for a base class" is somewhat ambiguous - if I read the post right it means specifying a value for the derived class's inherited fields by using an instance of the base class without copying, but in languages with more dynamic approaches to dispatch it would also be reasonable to talk about reassigning the base class itself (e.g. MRO tricks in Python). And "such piece-wise allocation" is indeed possible in various Lisp-inspired object systems.
  - scubbo 7y ago
    > scubbo's questions already indicate some knowledge of memory management I'm flattered! But no - I have a math degree, and the Java and Python that I'm familiar with are strictly high-level and self-taught from six years in industry * . I can give you an idea of my lack of knowledge of actual low-level details by saying that I know that the heap and the stack are different concepts in memory, but not how they differ in structure or use. Thanks for the link to CDR Coding - I'll work my way through that, and hopefully it will spur a lot more puzzled questions that I can then Google to continue educating myself! * plus I worked my way through Seven Languages in Seven Weeks a few months back, so I can fumble my way through understanding a Lisp (Clojure, if I recall correctly)
  - firethief 7y ago
    It does sound like they know something of a lisp-like programming model, but in C none of that is applicable because structs have fields at fixed offsets. In spite of lisp's obvious superiority, I think it could be useful to learn how the unenlightened languages people actually use do this stuff.
brianberns 7y ago
An object has to occupy a contiguous region in memory in order for dereferencing to work efficiently. We need both "this.baseField" and "this.derivedField" to directly access the desired bytes. If either of those has to chase through a chain of memory regions, performance will be much worse.
- morelisp 7y ago
  Statically-known field offsets are at least as important as contiguous memory; you can have either without the other, though a major "achievement" of classical OO is that a single-inheritance class gives you both without really thinking about it.
aw1621107 7y ago
I'm no expert, so take my answers with a grain of salt. > Why can the constructor not allocate memory "progressively" for the object as the construction chain descends the class hierarchy? I think it's a matter of allocating everything up-front being easier than the alternative. Even with a single-task OS/kernel and a single-threaded program, memory fragmentation could mean that a chunk of memory that is large enough to start construction wouldn't be large enough to finish it. As you mentioned, the OS/kernel could move the object under construction to a new chunk of memory, but there's no guarantee that the new chunk would be large enough, and performing said move is extra work that is relatively easy to avoid in the first place. > Sub-question - why does the memory for an object need to be contiguous? I think it has to do with a combination of predictability and efficiency more than it being technically infeasible. The predictability side is probably most important for systems programmers, who are also the ones who need to worry the most about allocation behavior. For them, control over object layout in memory can be important, and the choice between using "normal" members instead of pointers can be quite deliberate. Splitting objects across multiple allocations would necessitate inserting/dereferencing pointers regardless of what was written in the source code. This makes object size, memory access patterns, and potentially performance quite unpredictable. There are several aspects to the efficiency component: - The compiler cannot use fixed offsets to access fields of an object if the object can be split across multiple allocations at runtime. - There is additional bookkeeping required on the runtime (OS/kernel) to ensure that a split objects gets allocated/deallocated correctly. - Splitting an object across multiple allocations would require pointers to be inserted/dereferenced at some point or another. While you are correct in stating that RAM allows for approximately the same speed in accessing arbitrary memory locations, the same cannot be said for the CPU cache. Memory is quite slow compared to the CPU cache, and the cache is usually very limited in space compared to RAM. Thus, for optimal performance, you typically want predictable access patterns that are located in "close" memory areas. Pointers usually make doing so difficult, if not impossible. - Object size is no longer predictable, which is very problematic for more memory-constrained devices (or if you want to pack as much data as possible into cache). - Probably more I'm not thinking of at the moment > "But such piece-wise allocation is required if we want a record syntax were we can just specify a value for a base class." I don't understand this claim at all. Why is this required? What does it mean to "specify a value for a base class" - is this shorthand for "specify a value for a field of a base class"? I'm guessing that they mean that they want the ability to specify the values for the base class (or the fields of the base class) without having to allocate memory for the unused field(s) of the subclass(es) while still retaining the ability to specify subclass fields later.
panic 7y ago
I think the article is wrong here. This is the code it says won't work: struct Base { ... } struct Derived: Base { foo: i32 } impl Derived { fn new() -> Derived { Derived { Base::new().., foo: 92, } } } You don't need to allocate memory progressively to support initializers like this. You could allocate the entire Derived struct, copy the return value of Base::new() into the beginning of the allocated struct, then initialize the rest of the fields. If you wanted to avoid the copy (and deal with complications like internal pointers), you could even make Base::new() write its return value directly into the Derived struct's memory (like C++'s "return value optimization" does).

by scubbo 7y ago

firethief 7y ago

If you want to understand this article you'll need to learn a programming language like C. Once you know what the stack, the heap, and records/fields are you'll be able to ask meaningful questions.

morelisp 7y ago
It's weird to see a recommendation to learn C when 'scubbo's questions already indicate some knowledge of memory management - far more than you will learn "learning C". The suggestion to "allocate memory progresively" and not-necessarily-contiguously resembles Lisp cons cells, and the questions about how to handle conflicts are the first steps to inventing (and then finding the downsides of) https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding. The second question is also reasonable, "a value for a base class" is somewhat ambiguous - if I read the post right it means specifying a value for the derived class's inherited fields by using an instance of the base class without copying, but in languages with more dynamic approaches to dispatch it would also be reasonable to talk about reassigning the base class itself (e.g. MRO tricks in Python). And "such piece-wise allocation" is indeed possible in various Lisp-inspired object systems.
- scubbo 7y ago
  > scubbo's questions already indicate some knowledge of memory management I'm flattered! But no - I have a math degree, and the Java and Python that I'm familiar with are strictly high-level and self-taught from six years in industry * . I can give you an idea of my lack of knowledge of actual low-level details by saying that I know that the heap and the stack are different concepts in memory, but not how they differ in structure or use. Thanks for the link to CDR Coding - I'll work my way through that, and hopefully it will spur a lot more puzzled questions that I can then Google to continue educating myself! * plus I worked my way through Seven Languages in Seven Weeks a few months back, so I can fumble my way through understanding a Lisp (Clojure, if I recall correctly)
- firethief 7y ago
  It does sound like they know something of a lisp-like programming model, but in C none of that is applicable because structs have fields at fixed offsets. In spite of lisp's obvious superiority, I think it could be useful to learn how the unenlightened languages people actually use do this stuff.

brianberns 7y ago

An object has to occupy a contiguous region in memory in order for dereferencing to work efficiently. We need both "this.baseField" and "this.derivedField" to directly access the desired bytes. If either of those has to chase through a chain of memory regions, performance will be much worse.

morelisp 7y ago
Statically-known field offsets are at least as important as contiguous memory; you can have either without the other, though a major "achievement" of classical OO is that a single-inheritance class gives you both without really thinking about it.

aw1621107 7y ago

I'm no expert, so take my answers with a grain of salt. > Why can the constructor not allocate memory "progressively" for the object as the construction chain descends the class hierarchy? I think it's a matter of allocating everything up-front being easier than the alternative. Even with a single-task OS/kernel and a single-threaded program, memory fragmentation could mean that a chunk of memory that is large enough to start construction wouldn't be large enough to finish it. As you mentioned, the OS/kernel could move the object under construction to a new chunk of memory, but there's no guarantee that the new chunk would be large enough, and performing said move is extra work that is relatively easy to avoid in the first place. > Sub-question - why does the memory for an object need to be contiguous? I think it has to do with a combination of predictability and efficiency more than it being technically infeasible. The predictability side is probably most important for systems programmers, who are also the ones who need to worry the most about allocation behavior. For them, control over object layout in memory can be important, and the choice between using "normal" members instead of pointers can be quite deliberate. Splitting objects across multiple allocations would necessitate inserting/dereferencing pointers regardless of what was written in the source code. This makes object size, memory access patterns, and potentially performance quite unpredictable. There are several aspects to the efficiency component: - The compiler cannot use fixed offsets to access fields of an object if the object can be split across multiple allocations at runtime. - There is additional bookkeeping required on the runtime (OS/kernel) to ensure that a split objects gets allocated/deallocated correctly. - Splitting an object across multiple allocations would require pointers to be inserted/dereferenced at some point or another. While you are correct in stating that RAM allows for approximately the same speed in accessing arbitrary memory locations, the same cannot be said for the CPU cache. Memory is quite slow compared to the CPU cache, and the cache is usually very limited in space compared to RAM. Thus, for optimal performance, you typically want predictable access patterns that are located in "close" memory areas. Pointers usually make doing so difficult, if not impossible. - Object size is no longer predictable, which is very problematic for more memory-constrained devices (or if you want to pack as much data as possible into cache). - Probably more I'm not thinking of at the moment > "But such piece-wise allocation is required if we want a record syntax were we can just specify a value for a base class." I don't understand this claim at all. Why is this required? What does it mean to "specify a value for a base class" - is this shorthand for "specify a value for a field of a base class"? I'm guessing that they mean that they want the ability to specify the values for the base class (or the fields of the base class) without having to allocate memory for the unused field(s) of the subclass(es) while still retaining the ability to specify subclass fields later.

panic 7y ago

I think the article is wrong here. This is the code it says won't work: struct Base { ... } struct Derived: Base { foo: i32 } impl Derived { fn new() -> Derived { Derived { Base::new().., foo: 92, } } } You don't need to allocate memory progressively to support initializers like this. You could allocate the entire Derived struct, copy the return value of Base::new() into the beginning of the allocated struct, then initialize the rest of the fields. If you wanted to avoid the copy (and deal with complications like internal pointers), you could even make Base::new() write its return value directly into the Derived struct's memory (like C++'s "return value optimization" does).