Author Topic: Object-oriented design with Simon  (Read 6212 times)

0 Members and 1 Guest are viewing this topic.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Object-oriented design with Simon
« on: January 26, 2016, 01:01:00 pm »
Let's learn object-oriented design with Simon, part 1.

I feel this would benefit the NL codebase, and even the Lix codebase has a few classes that are still a bit too long. No idea who else will benefit, but maybe it's entertaining.

Two disclaimers
  • If this were 1995, OO would be hailed as the panacea of coding. In 2015, I will remind everyone that it's a design choice suitable for some parts of your program. It's your job to see whether it fits, or if it adds complexity that nobody needs.
  • NL might not get additional skills. In that case, don't trade a debugged design for undebugged theoretical soundness. The point of a design to minimize the cost of changing and maintaining it. If you aren't going to change much, don't refactor yet.
Code will be written in a Python-D-C++-Hybrid that I make up on the spot, but I hope stuff will be most clear like this. Indentation will replace begin/end.

The main principle is to replace if-else-if-else-if-else by dynamic dispatch. Whenever you have this:

if (lem.action == walker)
    lem.updateLemmingWalker()
else if (lem.action == faller)
    lem.updateLemmingFaller()
else if (lem.action == builder)
    lem.updateLemmingBuilder()
else if ...


We can do the following instead (a naive approach, with problems still). But it will dispose of the error-prone if-else chains for now.

abstract class Lemming:
    void update():
        do nothing

class Walker extends Lemming:
    override void update():
        check ground
        move ahead or turn

class Builder extends Lemming:
    override void update():
        produce brick or not
        check if out of bricks


Then we make a container object that collects Lemmings, and put the walkers, fallers, builders, ..., inside.

foreach (lem in container):
    lem.update();


If the lemming is a walker, this code will not call Lemming.update(), which would do nothing, but instead call Walker.update(). If the lemming is a builder, the code will call Builder.update(). The code calls the correct method without us knowing what the correct method is. The code calls the correct method without us having made an if-else chain to select the correct method.

There is a problem here, because the lemmings will want to change between classes. When the builder runs out of bricks, it wants to become a walker. But a class object shall never self-destruct and replace itself with another class, because it doesn't know which references to it should be updated.

Idea for that in the next post.

-- Simon
« Last Edit: February 10, 2016, 09:51:54 am by Simon »

Offline NaOH

  • Posts: 195
    • View Profile
Re: Object-oriented design with Simon
« Reply #1 on: January 26, 2016, 10:28:33 pm »
Is the idea composition?

I had the poor luck to be introduced to coding with object-oriented design. This was great when I was a naïve youngster, but now that I have explored different languages and paradigms, I have lost a reference point and I don't really appreciate the benefits of OO. Increasingly I'm viewing OO design principles as more limiting than they are helpful in shaping my code.

I realized something was wrong when a friend asked me, "so what is object-oriented design anyway?" and I couldn't give a clear answer. I'm no longer sure why it is that we put functions inside classes sometimes and call them "methods." The only benefit I can really see is polymorphism, but suddenly I feel like I'd be more comfortable with function pointers than dynamic dispatching.

Now, this opinion can't possibly be credible, because
Quote from: Simon
If this were 1995, OO would be hailed as the panacea of coding
so I'd like to watch this thread closely; maybe you can rekindle my affection for OO.

Offline ccexplore

  • Administrator
  • Posts: 4971
    • View Profile
Re: Object-oriented design with Simon
« Reply #2 on: January 27, 2016, 12:40:27 am »
The Wikipedia article on OOP does have a nice criticism section, so you're hardly alone in questioning the benefits of the paradigm.  Like Simon said, it's design choice.  People working on certain programming languages that have since become widely adopted in the software industry may have been smitten with the paradigm back in the 90s and introduced many of its features into their languages, but of course, it takes time and experience using the paradigm to fully understand the benefits and shortcomings.

Adding features to a language will of course increase its complexity, so in that sense it is understandable that some may prefer a language with less built-in features--you may have to write a little more code to do the same thing, but there's also less of a chance of getting tripped up by subtleties in the language's features.

In any case, in practice you rarely have a choice--except for the times when you're starting with no code written, whenever you have to work off from an existing codebase, the choice of language is usually taken out of your control at that point.  Even when you have the luxury to start from scratch, the choice of language may be limited by practical concerns, like how many people you can find that is proficient with a language.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #3 on: January 27, 2016, 03:35:28 am »
Awesome, this got replies. :lix-blush:

Quote
Is the idea composition? [...] Increasingly I'm viewing OO design principles as more limiting than they are helpful in shaping my code.

The idea is explicitly about when to choose polymorphic inheritance over composition. I found that useful for 2 parts of my own program: GUI, which is the classic application domain of class hierarchies. The second is lix activities, which have a very rigid, small interface -- switch to, perform, hooks on becoming and de-becoming -- and comparatively many implementations of these.

Inheritance incurs a design debt: By the Liskov substitution principle, "B extends A" requires that wherever an A is desired, we can pass a B to that, and the receiver can treat it like an A. We shall not curb functionality. This makes the resulting class hierarchy very rigid. Everything depends on the classes at the beginning, which become very hard to change.

Composition (class B { A a; ... } instead of class B : A { ... }) does not take up this debt. We don't have to expose any A functionality in B's interface. Some newer languages have features to forward any method call to B on to the component A as long as B doesn't implement them. This merges the convenience of not redefining methods from A with the convenience of not taking up any design debt.

The function pointers would work as well, and are idiomatic in C to get dynamic binding. We can make our own virtual table instead of having the compiler generate that from the class code.

Why then use the complex builtin language feature instead of composition or simple pointers? Leverage the compiler, let it check your work statically. This is a widespread mantra in D and C++. In D and the Java world, this is leveraged pretty strongly: On forgetting to implement an abstract method, the compiler will complain. On overriding a method marked final, the compiler will complain. The function pointers would instead crash at runtime to remind of necessary overriding.

In both cases, there's the option to interpret the error/crash as a mistake in the base class design, instead of as a welcome reminder.

When new classes are added, but the root classes remain the same, the if-else-chains would require updating code all over the application. There is no way to check whether one place has been forgotten. With virtual method dispatch, the changes are all bundled together in one specific place, the new class. If we expect our program to grow mainly in this manner -- a reasonable assumption with GUI components and lix skills -- then the class hierarchy might pull its weight.

Quote
In any case, in practice you rarely have a choice

Right right. Any kind of overarching design becomes encrusted and hard to change. OO is particularly prone to generate unnecessary rigid complexity.

Choice of problem domain, tooling ecosystem, and language, all of them have an influence on what overarching design is expected. I'm weird in that I love reading about professional software development, but only have a hobby project without any holy design to preserve.

OO with Simon, Part 2
Idea for can't-replace-self in container

We store lemmings, and the lemmings change their behavior during their lifetime. This leads to the following idea: Don't replace lemmings. Replace the behavior of lemmings.

class Lemming:
    private Job job
    void become(Job j):
        assert (j.lemming == this)
        job := j
    void updateCalledByTheGame():
        job.perform()
       
class Job:
    protected Lemming lemming
    abstract void perform():
        do nothing yet
    constructor(Lemming l):
        this.lemming := l
        this.lemming.become(this)

       
We introduce tight coupling between job and lemming here. (Both know of each other, and can access each other's public interfaces.) I have thought about this for weeks, and can't see how to get rid of it.

I'm also not as opposed to public/protected members as it's traditionally recommended to be. The reason is that in D, we can later rename the member and make it private, and write an accessor property method that's callable exactly with the syntax of the previously-public field. In other languages, you might want to encapuslate behind boilerplate immediately.
           
class Faller : Job:
    constructor(Lemming l):
        super(l)
    override void perform():
        lemming.moveDown
        if hit ground:
            lemming.become(new Walker(lemming))

class Walker : Job:
    constructor(Lemming l):
        super(l)
    override void perform():
        lemming turns or walks ahead
        if (no ground):
            lemming.become(new Faller(lemming))


My biggest dread is that this is overkill for the problem at hand. I had function pointers in C++ with a jump table. However, the C++ lixes had a fixed memory size. There were 2 ints reserved for each job to be used however they saw fit.

Using dynamically allocated classes allowed arbitrary private fields for each job. This has lead to much more expressive code inside the job methods. This expressiveness is not visible in my sample code above, because I'm focusing the hierarchy, not the exact method contents of any single job. But inside these methods, I've experienced the biggest gain in readability.

-- Simon
« Last Edit: January 29, 2016, 10:21:29 am by Simon »

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #4 on: January 29, 2016, 08:25:01 am »
OO and general design with Simon, part 3

Question that came up in IRC: In part 2, we wanted to solve the problem of self-replacing lixes. Of the following two solutions, what benefits does a) provide over b)?

a) Game manages non-replacing lixes, lixes have replacing jobs
b) Game manages replacing lixes

The answer is separtion of concerns. The game, or our physics model in general, is pretty complicated. It must deal with land, gadgets, lixes, have some interface to accept player input, etc. Whatever logic we can keep separate from the game at all, we should keep separate.

Compared with the game, the lixes are a smaller part of the program. The Lix class might end up longer, but it has less impact on the overall program.  They're still very complicated, but not as complicated as the entire physics model.

In our solution a), the jobs tell the lixes: We hit terrain, you have to take up another job. In solution b), the lixes tell the game: We hit terrain, you have to replace me. The game is already very busy, we should try not to bother it with such subtleties. However, in our a), writing detailed job-handling inside the lix class seems natural. Lixes are mainly about skills.

This doesn't have to do much with object-orientation. You can have this in any structured language. Classes with access modifiers are merely one way to separate concerns.

-- Simon
« Last Edit: January 29, 2016, 09:55:23 am by Simon »

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #5 on: January 29, 2016, 09:27:15 am »
OO with Simon, part 4
The clone() pattern

How to copy lixes around?

Deep copies (create a new object) instead of shallow copies (make new reference to existing object) are handy to implement savestates. We don't want this:

class Lemming:
    Job job
    copyConstructor(Lemming l):
        this.job = l.job

       
This would make a new reference to the old job, not what we want.

Now, a problem: How to make a deep copy of the old job? new is not polymorphic. The following code does not work.

class Lemming:
    Job job
    copyConstructor(Lemming l):
        job = new Job(l.job)
// error: Job is abstract, can't instantiate

abstract class Job:
    abstract void perform()
    copyConstructor(Job):
        ...
   
class Builder : Job:
    copyConstructor(Builder b):
        super(b)
        ...


Even if Lemming l is a builder, feeding l to Lemming.copyConstructor will fail to produce a new Builder job. There are languages with polymorphic new, but C++, Java, D are not among them. We're doing hard-ass 1990-style object-orientation here.

The standard solution is to write our own polymorphic method, which is idiomatically called clone().

class Lemming:
    Job job
    copyConstructor(Lemming l):
        job = l.job.clone()
// leave it to polymorphism to instantiate the correct Job subclass

abstract class Job:
    abstract void perform()
    abstract Job  clone()
    copyConstructor(Job):
// if Job has any fields, we still need this
        ...
       
class Builder : Job:
    copyConstructor(Builder b):
        super(b)
// initialize the fields of Job
        ...
// initialize the fields of Builder
    override Builder clone():
        return new Builder(this)


This code produces the desired effect: The game can make copies of lixes, unconcerned of what jobs they have. A lix, upon copy-construction, will instantiate a copy of the correct Job sublcass.

If your langague forbids overriding Job clone() with method signature Builder clone(), then instead override as Job clone() in the subclass. The above code will keep its meaning. D has covariant return types, which means that I may override as Builder clone(), and instantly qualify as a nerd for sneaking that term into a social discussion.

A downside of the clone pattern is verbosity. You have to define both copy-constructor and clone method in each subclass. And you have to define an overridden clone method in each subclass. Even if your language assists you with powerful compile-time code generation, you have to do it in every subclass.

-- Simon
« Last Edit: January 29, 2016, 02:05:09 pm by Simon »

Offline NaOH

  • Posts: 195
    • View Profile
Re: Object-oriented design with Simon
« Reply #6 on: January 29, 2016, 03:19:55 pm »
In C++, if Job is not stored as a pointer, won't the lemming be deep-copied automatically? The Job copy-constructor will be called implicitly and by default it will copy over each field.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #7 on: January 29, 2016, 03:42:52 pm »
In C++, if the lemming's job field is Job instead of Job*, there would be no polymorphism possible. Such a field cannot hold a builder job. Even when Builder doesn't introduce new fields, and therefore sizeof(Job) == sizeof(Builder), the memory layout doesn't necessarily match, for each object carries its own vtbl. (wrong, will make extra post). If we do this in C++:

Lemming lem;
Job job;
job = Builder(lem);


...the Builder would be implicitly converted to Job, then assigned to the static field.

This is a reason why Delphi and D make a semantic difference between struct/record with value semantics, and classes with reference semantics.

Complete example:

#include <iostream>

class A {
public:
    virtual void bark() { std::cout << "Hello from A\n"; }
};

class B : public A {
public:
    virtual void bark() { std::cout << "Hello from B\n"; }
};

int main()
{
    A val = B();
    val.bark();
    A* ptr = new B();
    ptr->bark();
}


$ ./a.out
Hello from A
Hello from B


-- Simon
« Last Edit: January 29, 2016, 04:35:51 pm by Simon »

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #8 on: January 29, 2016, 04:20:08 pm »
OO with Simon, part 5
Virtual function tables, specific to C++

Here are some declarations in C++.

class A { };
class B { int field; };
class C { int field; void method() { } };
class D { int field; virtual void method() { } };


How long are the objects of type A, B, C, D in bytes each? On the workstation in my office here, g++ -v says: Target: i686-linux-gnu, gcc version 4.6.3. The sizes of the objects are 1, 4, 4, 8.

The interesting difference is that existence of at least one virtual method puts an extra pointer into the class. This is a vtbl pointer. It points into a static vtbl, where the function pointers sit who enable dynamic dispatch. The vtbl is static in the C++-class sense of static, i.e., there is one vtbl per class.

A statically dispatched method is hard-wired to call the same method every time. On dispatching a method call dynamically, the code doesn't jump into a function immediately; instead it dereferences the vtbl pointer and jumps into where the vtbl points. In a class hierarchy, different classes may point to different vtbls. That's C++'s implementation of polymorphism.

Now, fields with manual function pointers instead of using the static vtbl would enable the following:

class Lemming {
    void (*jobMethod)(Lemming&);
    void perform() { jobMethod(*this); }
};
void performWalking(Lemming&) { ... }
void performBuilding(Lemming&) { ... }

Lemming lem;
lem.jobMethod = &performBuilding;
Lemming another = lem;


This would value-copy the function pointer, as NaOH has suggested. This is a difference to vtbls: In the example right here, each object points to a method directly. With vtbls, we point to a static immutable vtbl, which points to a method.

Yes, this obviates the need for the clone pattern. I haven't thought about upsides or downsides much yet.

-- Simon
« Last Edit: January 29, 2016, 04:48:52 pm by Simon »

Online namida

  • Administrator
  • Posts: 9354
    • View Profile
    • NeoLemmix Website
Re: Object-oriented design with Simon
« Reply #9 on: January 29, 2016, 11:19:17 pm »
I don't quite follow the technical terms or C-type code here; but I believe something like what you're describing is already how NeoLemmix handles different actions.

Code: (LemGame.pas 1353~1379 (in TLemmingGame.Create)) [Select]
// initialized once - this comment NOT present in actual LemGame.pas file, added for clarity here
  LemmingMethods[baNone]       := nil;
  LemmingMethods[baWalking]    := HandleWalking;
  LemmingMethods[baJumping]    := HandleJumping;
  LemmingMethods[baDigging]    := HandleDigging;
  LemmingMethods[baClimbing]   := HandleClimbing;
  LemmingMethods[baDrowning]   := HandleDrowning;
  LemmingMethods[baHoisting]   := HandleHoisting;
  LemmingMethods[baBuilding]   := HandleBuilding;
  LemmingMethods[baBashing]    := HandleBashing;
  LemmingMethods[baMining]     := HandleMining;
  LemmingMethods[baFalling]    := HandleFalling;
  LemmingMethods[baFloating]   := HandleFloating;
  LemmingMethods[baSplatting]  := HandleSplatting;
  LemmingMethods[baExiting]    := HandleExiting;
  LemmingMethods[baVaporizing] := HandleVaporizing;
  LemmingMethods[baBlocking]   := HandleBlocking;
  LemmingMethods[baShrugging]  := HandleShrugging;
  LemmingMethods[baOhnoing]    := HandleOhNoing;
  LemmingMethods[baExploding]  := HandleExploding;
  LemmingMethods[baToWalking]  := HandleWalking; //should never happen anyway
  LemmingMethods[baPlatforming] := HandlePlatforming;
  LemmingMethods[baStacking]   := HandleStacking;
  LemmingMethods[baStoning]    := HandleStoneOhNoing;
  LemmingMethods[baStoneFinish] := HandleStoneFinish;
  LemmingMethods[baSwimming]   := HandleSwimming;
  LemmingMethods[baGliding]    := HandleGliding;
  LemmingMethods[baFixing]     := HandleFixing;

Code: (LemGame.pas 6149~6150 (in TLemmingGame.HandleLemming)) [Select]
  Method := LemmingMethods[L.LemAction];
  Result := Method(L);

I'm not sure if there's a reason why the former actually initializes these values in the code, rather than using constants (it's like this in vanilla Lemmix too, and since it works, I never attempted to change it). Possibly Delphi doesn't allow referencing methods in constants.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #10 on: January 30, 2016, 05:48:41 am »
You have NL has manually tabled function pointers, and selects one manually every time during job performance. Tabling the pointers first only moves the manual if-else-if-else into a table elsewhere -- because there's only one place in the code where you dip into the table at runtime.

So, you're doing the current implementation is exactly what I consider problematic in part 1.

I will eventually make a longer post with the drawbacks. The main drawback is that we have to put any job-specific fields into the base class, but I want to argue in detail why that's problematic. Another drawback is that you have to maintain several tables of functions, without compiler help about forgotten maintenance.

-- Simon
« Last Edit: January 30, 2016, 06:21:04 am by Simon »

Offline EricLang

  • Posts: 382
    • View Profile
Re: Object-oriented design with Simon
« Reply #11 on: February 02, 2016, 09:58:18 am »
Quote
The main drawback is that we have to put any job-specific fields into the base class
When implementing the game-mechanics years ago, this was exactly the "philosofical" problem I ran into.
Imagine having different and more mechanics: then new variables / fields must indeed be added to the basic TLemming class.
I choose back then for convenience, simplicity and speed because of the relatively low amount of fields.

I once tried the idea of different classes for each state and came to the conclusion that it was not better. Far from it. "Transforming" a lemming into a new class seems "unnatural" to me.
So what could be a fast and simple and readable solution?

When looking at the original TLemming class, there are actually not so much fields and a lot the fields are used my each state, mostly regarding the animation.
When there would be too much "dedicated state fields" I think I would probably give (allocate) the lemming a "backpack" of specialized fields or maybe use some kind of "delphi cased record" trick.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #12 on: February 10, 2016, 12:37:53 am »
Quote
"Transforming" a lemming into a new class seems "unnatural" to me.

Yes, I agree that the lemmings should not be replaced. Many of their fields are persistent between jobs. Objects should model the real world: if we don't think of lemmings to be replaced, we shouldn't replace them. My proposed solution is to replace the behavior object instead.

This solution is compelling in hindsight. I have described its advantages in parts 2, 3, 4. But a class hierarchy is costly, even though it's idiomatic in OO design. To justify that cost, I will compare alternatives. It's a difficult design problem, and personal preference plays a role, too.

OO with Simon, part 6
Comparison of all-in-base-class, tagged union, and state pattern


Bloated single class: You put special fields for builder, special fields for faller, ..., all into the Lemming class. They're right next to job-independent fields like position or exploder timer. All fields are mutable, and all jobs can access everything.

Widespread access to mutable fields is a concern. Whenever you have a bug, you must inspect lots of code for how it affects the memory. The compiler cannot help.

Dispatching from the monolithic class via manual function pointers (end of part 5) doesn't solve the problem of widely-visible mutable fields.

Tagged union: I assume this is meant by the Delphi cased record trick. You reserve enough memory to hold the job-specific fields for any single job, and put this as a value field (struct, record) into the Lemming class.

Even though the builder variables now sit in the same memory location as the faller variables, you get to name them per job as bricksLeft and pixelsFallen.

This even more type-unsafe than the bloated base class. You can access the builder's fields even when you're a faller. But because they're in a union, not in separate locations, you overwrite the builder's fields when you write to the faller's fields.

A feeble benefit might be speed while making a savestate. You can memcpy the Lemming to save it entirely, and copy fewer bytes in total than with the bloated base.

State pattern: This is my solution explained in part 2. We make an abstract class for the behavior, subclass it many times, then have the lemming carry a dynamically allocated object for the behavior.

A lemming can have only one state at a time. It's not possible to access wrong fields, and the compiler checks that for you.

Old state objects don't cause long-term psychologic damage to the lemming when he gets a new state object of the same type.

Sometimes, you must access fields of different state classes nonetheless, especially during transistion between states. You can use an explicit dynamic cast -- which angers the object-oriented deities --, or write lots of specialized methods. And herein lie the problems of the state pattern.

About that, I would love to ask someone stronger than me at design for ideas.

NL might not get additional skills. In that case, don't trade a debugged design for undebugged theoretical soundness. The point of a design to minimize the cost of changing and maintaining it. If you don't want to change much, keep the existing thing.

-- Simon
« Last Edit: February 10, 2016, 02:02:04 am by Simon »

Online namida

  • Administrator
  • Posts: 9354
    • View Profile
    • NeoLemmix Website
Re: Object-oriented design with Simon
« Reply #13 on: February 10, 2016, 01:35:38 am »
Quote
NL might not get additional skills.

I can rule out adding any further skills in the near future; both the current level format and the current skill panel code and images would need significant changes to support it. When 7 new skills were added in V1.15n, it was coded in such a way that it left room for one further one, simply because parts of it (eg. the bytes in the level file that signify which skills a level has; which is a 16-bit value with an on/off bit for each skill) were often already well-suited towards adding a 16th. It was only a few versions later that one more was added.

Further down the line, it may be possible, but only if someone offers a very compelling reason to include a new skill. We already have two that very rarely see any use (although there have definitely been some levels that use them to excellent results) - the Disarmer and the Cloner. Even out of the remainder, the only ones that see a lot of use are Walker, Glider and Platformer.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #14 on: February 28, 2016, 05:13:24 am »
Object-oriented design with Simon, part 7
"Object" must be empty

It is an egregious offense to call a self-defined class Object or Instance.

If you name your own defined classes Object or Instance, you will unnecessarily overload human language. There is always a better name than Object, and almost always a better name for Instance.

The only merit to have a class Object is to have a universal root class. D defines Object as such, which would be no problem if it were an empty class, usable like C++'s void*. But this was before D got powerful templates. Therefore, Object defines opEquals as a hook to override == instead of leaving comparison to templates and duck-typing. I ran into subclassing problems intrinsic to D's Object.

D is still a low-Simon-rant-% language. :>

-- Simon
« Last Edit: February 28, 2016, 05:32:57 am by Simon »

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #15 on: April 11, 2016, 09:03:52 am »
Part 8: Sucky performance of OO -- but is it the lion's share of my problem?

There's a performance downside to the state pattern in part 6.

Naively, with automatic memory management, we allocate a class instance for the lemming, then a class instance for the job. We don't estimate the maximum memory size to fit all jobs, but allocate dynamically per subclass. The lemmings go in a collection of pointer-to-lemming, and point themselves to their jobs. When we copy n Lemmings, we follow 2n pointers, and allocate 2n little chunks.

The tagged union is faster. All lemmings occupy the same amount of space: job-independent fields, plus the maximum length among all jobs. You can allocate naively n lemmings, or put them in an array that allocates once. Similarly, all-fields-in-base-class allows to allocate once.

In D/A5 Lix, I've implemented the naive strategy. In addition, I allocate entire savestates under the garbage collector, then run the garbage collection whenever savestates become superfluous. Savestates contain VRAM bitmaps of the land, in addition to the lixes and jobs. To preserve VRAM that's managed by the savestates, I run the RAM garbage collection multiple times per second during framestepping. But running the GC may hit performance much harder than a slow allocation strategy.

Related to my strategy:
Discussion with ccx about a crash due to exhausted VRAM
github issue: before running the GC often
github issue: performance of running the GC often

I would like faster savestating, aiming at faster framestepping. I should compare the performance gain of (D/A5 Lix now to D/A5 Lix with manual savestate management, without running the GC, but still 2n allocations each savestating) with the performance gain of (2n allocations to a single allocation for lixes).

I want to feel good. I want huge gains in VRAM management; I want negligible prospects in hacking up the job hierarchy. I wouldn't like my OO design responsible for my problem... at least this time. :lix-grin:

-- Simon
« Last Edit: April 11, 2016, 11:31:13 am by Simon »

Offline ccexplore

  • Administrator
  • Posts: 4971
    • View Profile
Re: Object-oriented design with Simon
« Reply #16 on: April 11, 2016, 09:54:07 pm »
Even if you run the GC less often, it seems like it may just possibly defer the overhead to happen in one go later, so instead of constant slow framerate, you may just end up with mostly okay framerate punctuated every now and then by a total stutter from the eventual GC.  Which may still be preferable; just want to point it out.

That being said, it might be possible to reduce how frequently you run GC in order to deal with VRAM exhaustion, without abandoning automatic memory management completely.  Under the assumption that the main problem is because D's GC is not aware of video memory allocations associated with A5, at the points where you are actually making the calls to A5 to allocate and deallocate, you can also track an estimate of how much video memory has been allocated so far.  Then whenever you're currently looking at running GC to mitigate VRAM exhaustion, you can check the total allocation estimate first, and only run the GC when it actually exceeds a certain threshold (possibly user-configurable as a troubleshooting mitigation).

Reducing number of class instances and pointers should theoretically help with performance of GC, since it is generally based on walking those instances and pointers, but obviously it's hard to be certain of the effectiveness without some sort of detailed profiling.

One other random thought: you mention faster framestepping as the motivation, but I kind of wonder if maybe a possible solution there is some sort of frame-dropping instead (as long as it's not excessive of course).  I'm just not sure how critical it is to have perfectly smooth framestepping, given that in a lot of cases, I imagine you first get it going continuously to get to the ballpark of where you want, and then you start manually hitting the key more slowly to truly step one-by-one.  The first part seems like the only part where speed matters, and if it's just about getting to the ballpark, frame-dropping could potentially be an acceptable mitigation?

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #17 on: April 12, 2016, 06:05:20 pm »
Great ideas!

I love the frame-dropping during ballpark-framestepping. The fastest method for backstepping goes back 15 steps per graphics frame, even when the FPS drop below 60. Instead, the feature should go back (15 * 60 / FPS) steps, to cancel performance hits.

Yeah, I haven't profiled enough for the question in part 8. I work on D Lix sporadically, mostly on the editor. When I get loose ideas for physics, they go on the backburner. Manual savestate RAM/VRAM management smell best to me. Still, I'll keep the alternatives in mind.

-- Simon

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #18 on: May 05, 2017, 12:45:58 pm »
Lesser of two globals

Mutable global state is a source of bugs; avoid if possible. This is joseki standard knowledge.

But even immutable globals bite you in the ass. The medium font is a global? Let's export things as images that are independent from screen size, then immediately continue to draw to screen afterwards. Maybe add decoration that silently depends on resolution to our unscaled exported image. Load and destroy the independent medium font and the scaled medium font back and forth?

One answer is to wrap this in a drawing context, load and cache multiple drawing contexts lazily. The first time I draw to screen, a context loads the scaled font. The first time I export as image, another context loads the unscaled font.

Switch between these contexts by mutable global state, because it's rare to switch? <_<

-- Simon

Offline ccexplore

  • Administrator
  • Posts: 4971
    • View Profile
Re: Object-oriented design with Simon
« Reply #19 on: May 06, 2017, 12:08:50 am »
I think the problem statement is a little vague for those of us who don't work closely with the D-lix codebase.

The drawing context idea seems like a good solution based solely on what you described.  I'm not sure why you still need to switch state?  The idea for introducing drawing context would implicitly mean that your drawing operations should always be explicitly given a particular drawing context to use (potentially you can make null or some other similar convenience value to mean using a "default" context, that can be global and immutable).  It sounds like you would want a separate "export image" drawing context that would only be used for the export case.  If you want, you can make that second drawing context a second global.

I don't know that it's even really fair to blame this on using an immutable global per se.  What that really translates to, IMO, is that you simply didn't anticipate the need for multiple drawing contexts to begin with, specifically that there is a need for scaled and unscaled fonts, due to differences between drawing to screen and exporting as images.

Offline ccexplore

  • Administrator
  • Posts: 4971
    • View Profile
Re: Object-oriented design with Simon
« Reply #20 on: May 06, 2017, 10:05:09 am »
Incidentally, (temporary) switching of globals may not be that bad if you manage it through a RAII helper class whose purpose is basically to override the global for the duration of the lifetime of the helper class (and restoring to the previous value upon finalization).  Of course this assumes certain patterns usage such as no multithreading.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #21 on: May 10, 2017, 03:47:38 pm »
Yes, I like RAII helpers in similar situations. I wrapped target bitmaps or blenders in them, these are Allegro thread-local.

Lix is entirely single-threaded. There is theoretical potential to parallelize: D has all mutable variables thread-local by default, Allegro 5 drawing routines have a global drawing target per thread. But multithreading is daunting and my early dabblings in 2015 to parallelize crashed.

In my application, the drawing context switches so rarely that I'd rather not clutter the GUI elements' interface. But enlarging that interface is a good solution in general.





Fruit basket problem

(Source: Object-Oriented Design Heuristics, by Arthur J. Riel)

You have a class Fruit, with subclasses Apple, Banana, Orange. In particular, Apples know how to core themselves. And there is a container class Basket, this collects Fruit and allows you to insert and iterate over the fruit. We have lots of different fruits in the basket. How do we iterate over the fruits, telling the Apples to core themselves, ignoring other types of fruit?

The Smalltalk solution is that you tell every fruit to core itself. Calling core on a Banana would be legal even if Banana doesn't understand this, and the banana would do nothing. (Wrong, see 2 posts further down.) The problem becomes much harder in D, C++, or Java; here, it's illegal to call core on Fruit. I like strict static analysis and want the compiler to yell at me.

Proposed solutions:

Fat interface: Make an empty method core in Fruit. Override this only in Apple with the meaningful behavior. Call core on every fruit in the Basket. Downside: Fruit gets special knowledge of Apple behavior. But maybe this is the least intrusive solution.

Explicit analysis: dynamic_cast<Apple*> every Fruit*. This returns null if we have a banana or orange. Call core on what casts successfully to Apple. Downsides: The fruit basket problem is far too common. Explicit case analysis everywhere is exactly what OOP tries to avoid. Instead of littering the entire codebase with special-casings, we should centralize all this special-casing in classes Fruit and Apple. We'd get OOP's verbosity without reaping its benefits.

Apple-knowing Basket: Consider Fruit and Apple correctly designed, but Basket ill-suited for our purpose. By definition, the Basket returns Fruit references, and calling core on Fruit is not allowed. Instead, the Basket should privately maintain a list of Fruit references, and, separately, a list of Apple references that point to the same objects as the Fruit list points to. Downsides: What is the Basket's interface to add elements? Will it dynamic-cast, or should Basket's caller make sure he calls addFruit and addApple correctly? What happens if Basket's caller gets their Fruit from a Fruit source that doesn't support this pattern?

-- Simon
« Last Edit: September 27, 2017, 08:36:07 pm by Simon »

Offline ccexplore

  • Administrator
  • Posts: 4971
    • View Profile
Re: Object-oriented design with Simon
« Reply #22 on: May 10, 2017, 07:57:10 pm »
Hmm, apple-knowing baskets frankly sound like a hack that doesn't really scale all that better than explicit analysis or fat interface.  If peeling fruit becomes a thing (let's say for purpose of discussion, some fruits like strawberries can't be peeled, even though I'm guessing technically they probably still have some kind of peel in terms of biology), does the basket now also need to track that separately too?  What if I want to carry my fruits in a tray instead, does the tray now have to copy all the special-casing that the basket is doing?

How does Smalltalk handle the case where the method being called would normally return a value?  If you try to invoke the method on an object that doesn't actually support the method, what happens?  Does the invocation attempt still return some sort of default or special value (think null or undefined or similar) for that case?  It seems to me even in Smalltalk, you may not be able to always take advantage of the feature where it silently allows methods to be invoked on unsupported types.  Even if the language guarantees some sort of well-defined return value in the unsupported case, its semantics may not always be what you want for downstream calculations/processing utilizing the return value, and in such cases it could be better or even required to check for support-ness upfront instead.

Ultimately, regardless of language support, what ends up happening "under the hood" is that the check will be made one way or another, whether implicitly by the language (eg. Smalltalk would effectively be doing the check for you of whether the method exists for the target object) or explicitly by the programmer.  For languages where it must be done explicitly, it just becomes a matter of if/where/how you want to "hide" the check.

In some cases you can also simplify the manual checking by, for example, requiring fruits to implement an ICoreable interface if it supports coring.  So you just have to check for ICoreable and not more explicitly for specific fruit types.

I do agree that the situation you are describing [ie. abstracting out the pattern of "if (supported) dothis() else /* do nothing */"] is not uncommon, and it would probably be useful for commonly used languages to support that case better.

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #23 on: May 10, 2017, 08:34:24 pm »
Good reply, I googled some more.

Errata: Smalltalk won't let you call nonexistant methods on objects by default, that's a runtime exception. You could redefine the nonexistant-method handler in your classes, but that would be considered a massive hack.

Smalltalk lets you call existant methods on null references, and does nothing. This is much different and doesn't help with the fruit basket problem.

Will come back for the rest!

-- Simon

Offline Colorful Arty

  • Posts: 759
  • You are so loved!
    • View Profile
    • Colorful Arty's Youtube Page
Re: Object-oriented design with Simon
« Reply #24 on: May 10, 2017, 10:16:43 pm »
I like this scenario. My first instinct would be to create a boolean attribute for Fruit named isCoreable and then give the subclasses of fruit that are coreable the core() function. Then, you can check each fruit, check if its attribute isCoreable is true, then call the method core().

I know for sure this is not optimal, which is where you could have the subclasses of Fruit that are coreable implement an interface that lets them be cored. I'm not sure how many languages use interfaces, but Java does, and Python can use abstract classes instead to solve the problem.
My Youtube channel where I let's play games with family-friendly commentary:
https://www.youtube.com/channel/UCiRPZ5j87ft_clSRLFCESQA

My levelpack: SubLems
For NeoLemmix: http://www.lemmingsforums.net/index.php?topic=2787.0
For SuperLemmini: http://www.lemmingsforums.net/index.php?topic=2704.0

Upcoming levelpack: ArtLems
Development Topic: http://www.lemmingsforums.net/index.php?topic=3166.0

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #25 on: May 10, 2017, 11:09:07 pm »
apple-knowing baskets frankly sound like a hack
need to track that [peeling] separately too?
carry my fruits in a tray instead, does the tray now have to copy all the special-casing that the basket is doing?

I assume the work grows too quickly here, yes.

I don't dare to propose a Basket<mainClass, subclass1, subclass2, ...> with compile-time code generation, even when that's probably possible. :lix-suspicious: Maybe this is truly the land for dynamic typing without any static checks at all? But even those raise errors on unsupported methods...

Quote
How does Smalltalk handle [...] still return some sort of default or special value (think null or undefined or similar) for that case?

Most of this is answered by "I erred and Smalltalk doesn't allow it by default." The Smalltalk nil object responds to all messages that the class would normally respond to, and returns the nil object. This looks OK because everything is an object in Smalltalk.

Quote
For languages where it must be done explicitly, it just becomes a matter of if/where/how you want to "hide" the check.

Wise interpretation. The three proposed suggestions happen give the three possible answers: The check can go in the element class, in the client code, or in the container class. I didn't see this! :lix-scared:

Quote
I do agree that the situation you are describing [ie. abstracting out the pattern of "if (supported) dothis() else /* do nothing */"] is not uncommon, and it would probably be useful for commonly used languages to support that case better.

Nnnnn, thanks. :lix-grin:

Quote from: Colorful Arty
create a boolean attribute for Fruit named isCoreable and then give the subclasses of fruit that are coreable the core() function. Then, you can check each fruit, check if its attribute isCoreable is true, then call the method core().

Yep, this looks like a variant of the fat interface. The Fruit class gets some Apple-specific knowledge.

If you define isCoreable in Fruit, and core() only in the subclasses, then you still have to cast in the client code.

Quote
subclasses of Fruit that are coreable implement an interface that lets them be cored. I'm not sure how many languages use interfaces, but Java does, and Python can use abstract classes instead to solve the problem.
Quote
In some cases you can also simplify the manual checking by, for example, requiring fruits to implement an ICoreable interface if it supports coring.  So you just have to check for ICoreable and not more explicitly for specific fruit types.

This is excellent when we don't like to put everything right in base class. The example becomes Banana : Fruit; Orange : Fruit; Apple : Fruit, Coreable.

Defining the Coreable interface is probably wise even if we do it solely for explicit dynamic casting later. Coring seems to be a central concern in our domain, otherwise we wouldn't worry as much about this particular design problem. We can well abstract that into an interface and dynamic-cast to that.



Bonus: Found a webpage with the exact section from Riel's book! I bought the hardcover second-hand last year, it was splendid bedtime reading. At least if you believe that OO is often good. :lix-laugh:

-- Simon
« Last Edit: May 10, 2017, 11:42:21 pm by Simon »

Offline NaOH

  • Posts: 195
    • View Profile
Re: Object-oriented design with Simon
« Reply #26 on: April 01, 2019, 06:01:12 pm »
Forgive me for appearing out of nowhere to respond to this old thread, but I was thinking about this issue recently.

The tagged union is faster. All lemmings occupy the same amount of space: job-independent fields, plus the maximum length among all jobs. You can allocate naively n lemmings, or put them in an array that allocates once. Similarly, all-fields-in-base-class allows to allocate once.

Could you perhaps leverage placement-new in order to store all the jobs in a contiguous memory region, which you could then copy all in one sweep with memcpy() in order to make savestates?

Offline Simon

  • Administrator
  • Posts: 2710
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #27 on: April 02, 2019, 05:38:12 pm »
Could you perhaps leverage placement-new in order to store all the jobs in a contiguous memory region, which you could then copy all in one sweep with memcpy() in order to make savestates?

Yes, I've started to emplace in late 2017. But the array is not purely an array of Job. The memory layout in Lix is like this:

+------------+------------+------------+------------+----
| Lix 0      | Lix 1      | Lix 2      | Lix 3      |   
|    +-------+    +-------+    +-------+    +-------+ ...
|    | Job 0 |    | Job 1 |    | Job 2 |    | Job 3 |   
+----+-------+----+-------+----+-------+----+-------+----

Each Lix object contains a Job region, and the Job is placement-new-ed into the Lix object. Job is still a polymorphic hierarchy. The Job region is large enough to take any subclass.

It's not 100 % memory safe because old Job code could run while the Job region has been overwritten with a different Job. But it's a tradeoff for speed, there are runtime assertions, and also D has static if to test at compile time that each Job subclass fits into the reserved region.

To the outside, each Lix including her Job behaves like a value type. You can savestate the array with memcpy.

I've begun to read Effective Modern C++, it's nice to see that C++ is catching up with memory management and compile-time features.

-- Simon
« Last Edit: April 02, 2019, 05:48:53 pm by Simon »