The week that wouldn't end (job stuff)
I've finally come to realize that I'm happiest when I'm learning things. I mean, as much as I hated working for John nearly a year ago, I did learn a lot of interesting stuff about telecommunications and so on which I would have never learned otherwise. And, of course, my current job has involved a lot of learning of various things (different mobile platforms, the inner workings of the games industry, etc.), and currently I'm doing something which actually makes me happy!
Right now I'm finally learning Java for reals, working on the MIDP port of Sprung. Though I think I've already finished the "learning" stage of things, having learned about Class.forName which is just one of those "OMG" moments which makes me realize that, for all its gimpiness, Java has some really neat language features — unfortunately, as a whole the platform is kinda frustrating. Still, it's very gratifying to see that Java's object model is actually very similar to ObjC's in a few ways (like having protocols, which Java calls interfaces). Learning ObjC (with the intent of porting Solace's graphics framework to OSX as native Cocoa) was also a lot of fun, even if I haven't actually written anything meaningful in it yet.
Though it'd be really nice if you could get type-safety on interfaces like with ObjC's protocols (in Java you use a typecast to tell the object to use a particular interface, and just hope that you happen to be typecasting something which exposes said interface or otherwise be good about catching exceptions or whatever).
Multiple inheritance is way more generic (and a bit easier to work with in some ways), but it's also way more foot-shooty. Which is why I've never actually used MI in a project.
Anyway, right now I have a pretty basic skeleton MIDlet which will detect whether the display is capable of using a full-screen canvas or not, and start up accordingly. I was kinda flailing about at doing it myself for a while until I came across Nokia's "BlockGame" example which shows how to really do it. Fortunately, it turned out that I was already doing it the right way (yay me!) and the only bit I was missing was the aforementioned Class.forName thing. (It queries the system for a class matching that particular name, and throws an exception if it's not found. Basically it wraps up the entire useful functionality of COM and CORBA into a single convenient little call. Then there's other fun stuff for wrapping up class constructors as a generic functor which are exceedingly ugly and yet surprisingly elegant.)
Oh, and so then after that it just hands off to the game manager object, which then delegates drawing and input handling to various other fun objects. For now the only implemented object is a simple graphics test to familiarize myself with MIDP graphics though. It runs on every MIDP phone I've been able to throw it at, namely Borland and Nokia's various MIDP emulators, the Nokia 6600 we have at work, and my N-Gage QD.
The N-Gage, incidentally, is a bit faster than the 6600 (about 25%ish), based on the size of the retrace shear bands I get when I just continuously fill the screen with a random color. Also, even though the N-Gage uses an older version of Symbian OS and only supports MIDP 1.0, the system as a whole feels newer and more polished than the 6600, which uses the latest released-in-hardware version of Series 60 and supports MIDP 2.0. Like, the entire user experience as a whole just feels much more streamlined and efficient but also more flexible, like the difference between OSX 10.2 and 10.0 — same underlying system and overall UI scheme, but WAY easier to do things.
It probably won't be fast enough to do a lot of the fun graphics stuff we've taken for granted on the other platforms, though. Does anyone know if it's possible to replace a PNG's palette on the fly in MIDP 1.0? I haven't yet figured out how to parse Sun's MIDP docs in a meaningful way (JBuilder's crappy help browser doesn't really help, either).
Anyway. Now that I've finally tasted the forbidden fruits of Java in a meaningful way (and not just in an "introduction to programming languages" way), I think I really like a lot of its language concepts. Of course, the ones I like the most are the ones it unapologetically borrowed from Objective-C, but Java's take on the Smalltalk object model just seems so much more refined. But there's a lot of stuff I really miss from C++, such as
- operator overloading
- templates (though interfaces mitigate this somewhat)
- a preprocessor (I feel like I could kill to get #if 0/#endif again!)
The tag mechanism would still be there, obviously, it's just kinda dumb to have temporaries be treated with the same level of potential permanence as your main app control delegate, or whatever. Especially since doing instant refcount-based deletions means the GC doesn't have to run as often.
Another thing I don't like about Java is its inherited constructor syntax, if only because it's kinda vague. Like, in C++, it's pretty explicit (and obvious) about when an inherited constructor is called (and which one is called), but in Java it just seems kind of ambiguous; like, can you call super(...) at any time in the constructor, or does it have to come first? If you call it later does it mean the inherited constructor is called after part of the subclass constructor has already happened? What if the subclass constructor references protected members or non-static inherited methods? What if the subclass constructor signature matches a constructor signature of the inherited class and you call a different inherited constructor explicitly? What if you call the inherited constructor more than once?
Mostly I just don't like it because it seems like if you don't explicitly call the inherited constructor, it won't get called. This is why I prefer C++-style initializer lists. It also just seems un-kosher to call a constructor directly, but of course that's also probably since I've been coding primarily in C++ for like 7 years now. (Though obviously I'm not set in my ways, nor do I think that one particular way is the best.)
Speaking of coworkers who disagree, Neill has turned out to be even more awesomer. He's rewritten a lot of my framebuffer stuff to make it way more efficient (mostly because I was assuming that the compiler would be smart enough to inline methods which I'd explicitly marked as inline — silly me! — so he rewrote them as macros and also found a few other clever speedups and so on), and then gone and done some pretty clever speedups on some of the BREW phones which I would have never considered doing (because I respect the sanctity of a black box unit). So, he's managed to expose a raw framebuffer on phones which don't support BREW's "raw framebuffer" object. Very clever.
Also, a few days ago, I made the mistake of referring to a crappy BMP wrapper as crappy when its author was listening. But I didn't mean crappy as in "poorly-coded," just that it was crappy in terms of it being a trivial and naive way of doing it, which just happens to work most of the time (and also being the way that most people do it anyway, even though it causes lots of problems with endianness and alignment, including on the particular processor we're doing it on). He asked that I not call his code crap. I said I didn't call his code crap, I just called the method he was using crappy. He said, "Just shut up, okay?!" thus brilliantly winning the conversation, before I could go on to explain that a lot of the code I've written is similarly crappy, and that it wasn't the code itself I was calling crappy. Surprisingly, it didn't get out of hand or turn into yet another stupid explosion on this person's part, but of course he's probably written it off as yet another case of me thinking my way is the only way to do something because he didn't even want an apology for a dumb offhanded comment which he interpreted in a different way than I intended. Le sigh.
Oh well. This particular other person seems to assume that the only reason I think his code has room for improvement is because I think my code is perfect and everyone should look up to me as a programming deity, which is definitely not the case. I kinda miss the days when I felt like I was taking him under my wing and teaching him in the ways of code-fu, but somewhere along the line, tension built up, he decided I was just an arrogant prick for daring to think that my years of hobbyist and semi-professional programming experience actually meant anything compared to his two-year associate's degree, and I lost interest in trying to make an effort to help him learn.
I try to pretend that I'm okay with that and that I don't care what he thinks anymore, but I still feel like I've failed. I mean, I used to teach a university-level C++ course (and before that I was the teaching assistant for other courses, including computer graphics), but always felt like I did much better in a one-on-one setting. Of course there were always problem students who just wanted to pass and didn't want to learn... but it's different when it's a coworker.
Comments
I'm trying to get an article together called politics-oriented software development, but it seems to want to keep turning from a useful-real-world-advice thing into a bitchfest...
The GC thing is one reason why Java is substandard for client apps. There's a wierd mental block about it in the Java camp. If the user clicks on a button, you have only a couple hundred milliseconds to respond before they call it "slow". You can't explain to the user that the GC just happened to decide to collect dead memory.
It's why Java works so much better as a server language despite being, in theory, designed for clients. In a server, freezing everything to collect for half a second isn't an issue. For a server, you want high transaction throughput and low transaction time. For a client, lower maximum response time is more important.
ucblockhead: I'd heard that C# was basically a combination of the best parts of C++, Java, and Delphi (and was actually designed by the guy who designed Delphi) and I do want to learn it someday, but unfortunately it's not what cellphones use. Currently, cellphone games fall into three camps:
- BREW (C/C++ with a horrible COM-like interface which was a good idea in theory but implemented really badly because they didn't actually start making the interfaces useful until 2.0, so now all the phones with a decent API also need to support the craptacular 1.x API while programmers need to do all sorts of tricks to do stuff which will work on both); used by most Verizon phones, and Qualcomm (its creator) is trying to get other providers to support it as well, though as a platform (BREW is an entire operating system, not just a gaming API), BREW really sucks and is hard to use and confusing and blah
- Symbian (C++ with a pretty decent native API which was actually well-thought-out) which basically only Nokia and Ericsson use, even though it's (IMO) the best smartphone OS out there right now, and pretty close to awesomest for a PDA (though IMO, PalmOS still beats it overall)
- Java MIDP, supported by pretty much every phone out there now, though levels of support vary and none of the phone manufacturers tell anyone any of the information important to developers (CPU speed, maximum application size, level of profile support, etc.)
Although Symbian is definitely the best of these three platforms in terms of gaming support and overall user experience, we're not planning a native Symbian port since although it has a pretty decent install base these days, it's not among the general public that we're targeting; it's more of a high-end phone for business users, and the only gamers who have it are the ones foolish enough to get an N-Gage. (I specifically got an N-Gage because it's based on Symbian and is a lot cheaper than the other Symbian phones. I certainly didn't get it for gaming!)
And anyway, our target market is casual cellphone owners who want something to do while sitting on the subway, and not gamers per se. Much larger market.
Also, Symbian devices all support MIDP, so supporting MIDP means getting Symbian as a side-effect. Unfortunately, since Symbian phones use KVM instead of anything with JIT (though so far I don't know of any cellphones which do JIT), MIDP games need to either have pretty high-level graphics or will be really slow. Sprung's graphics can be mostly high-level (just blitting PNGs or whatever), though we're really going to need the ability to modify the palette on-the-fly to do the various color/brightness/saturation effects which the writers have come to rely on.
I also just realized that this is probably the most densely acronym-packed comment I've ever written.
* The refcount has to be updated constantly, whenever the object is assigned to a variable or passed in a parameter. This has a lot of overhead.
* The refcount uses up space in every object. Even a 2-bit refcount means you have to find two free bits in the object header, which may not be possible. (Also, tiny refcounts are more expensive to manipulate since you have to do masking.)
* The Achilles' heel of refcounting is that cycles of objects that point to each other won't ever be deallocated. In environments that use refcounting (like Cocoa) the programmer has to deal with this by explicitly clearing pointers on cleanup, or by making one direction of pointer non-ref-counted. But Java programs don't do that.
Basically it turns out that in the end refcounting is *more* expensive than true GC techniques. As you point out, it's highly incremental and objects can be freed quickly. It's also trivially simple to implement and understand, which is why it's still used a lot, especially in environments where not all the memory is automatically managed. But if you're going all the way to GC, other techiques are more efficient.
Java doesn't generally use mark-and-sweep, as you said. Most garbage collectors now are generational copying. This makes allocating new objects extremely cheap (it's basically a pointer-increment followed by a compare). If references to the object don't last long, it won't get saved in the next GC cycle so there's little extra overhead in having allocated it.
Garbage collection is a really, really complicated topic that has absorbed a lot of academic research over the past 40+ years. I've spent some time reading about it but I definitely don't consider myself an expert. It turns out that nearly any bright idea you or I might have about how to do it better, was already thought of at MIT in the '60s and either implemented or abandoned as impractical. The best introduction I've seen is Paul Wilson's classic paper:
http://citeseer.ist.psu.edu/wilson92uniprocessor.html
I highly recommend reading this if you like thinking about twisty algorithms and data structures!
Actually, for the situations I was thinking of, even just a one-bit refcount would be useful - 0 means "only one reference" while 1 means "lots of references." So it'd be more of an early tag for a fast sweep path. And the mask operations for that would be totally trivial (like, header.blah |= 0x80 when something else references it, and, like,
if (!(obj.blah & 0x80)) sweep(obj);when it's unreferenced).Also, a cleaner way to deal with cycles in many cases is to have a container object which knows about the graph as a whole; when the container object is freed it'd clean up the graph. IMO "cycles kill refcount" is a bit of a red herring since cycles don't seem to come up that much anyway.
The problem with a 1-bit refcount is that almost any object, even a temporary one, ends up with a refcount > 1. Obviously when you call 'new' the object ends up with at least one reference (from the local you assign it to.) If you then pass that object to a method, or put it in an array or in a field of another object, or even assign it to another local, it gets at least one more reference.
But if you make the refcount bigger than one bit, then you have to worry about thread safety when you modify it. That makes it a lot more expensive than the single OR operation you gave as an example. In fact, it makes it more expensive than using a full 32-bit refcount because you have to detect the overflow case.
Yes, you can have a container object that cleans up the graph. It's just a different way of manually cleaning up cycles. My point is that the application code has to be aware of cycles and cleaning them up. This is a pain, can easily lead to leaks, and it means you don't have automatic memory management any more. It also means you could never use such an implementation in a runtime for an existing GC language because existing code doesn't do this sort of cleanup, so your runtime would leak memory.
Cycles do come up a lot. For example, in any view/component system like AWT or Swing, every component points to its container, and every container has an array of components. In an event-listener model like JavaBeans, the event producer points to its listener(s) and the listeners generally point to the producer.
Like I said, it's complicated. Read through the section on refcounting in the Wilson paper! They really did go through all this stuff in LISP and Smalltalk interpreters. (Smalltalk-80 used refcounting and we did have a lot of trouble with cycles, believe me.)
I'm just trying to think of ways that Java could be more graceful about code like, say:
for (int i = 0; i < 100; i++)
{
int j = i*2;
System.out.println("i = " + i + " j = " + j);
}
which normally creates 100 temporary ints and something like 500 temporary Strings (i.toString(), j.toString(), and the various intermediate concatenations thereof), if my understanding is correct.
Though your example of AWT and Swing made me realize that there are a lot more cycles in stuff than I'd really thought about - for some reason I was only thinking of directed graphs of objects and so on, and forgot that the very app I'm developing has plenty of cycles (for example, SprungMIDP references Game, which in turn references SprungMIDP).
ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps
That's a raw PostScript file, but Preview on OS X can display it (although the font looks pretty blotchy.)
It's a great paper, very readable. At least check out section 2.1 on ref-counting; it should address most of what you've been saying.
BTW, explicit refcount (as seen in COM, CORBA, BREW, and ObjC) is a pain in the ass, and I'm certainly not arguing in its favor.
Your example's actually a good one because, if you looked at the source code to those String methods that get invoked, they do a lot more than you might think. I'd guess that the refcounts of the various String objects being created end up with refcounts of at least 5 as they get passed through various levels of library methods. (Oh, and your example doesn't create any temporary ints. Ints aren't objects.)
What happens with a good generational collector is that each object created during that loop is allocated simply by bumping the "freespace" pointer in the new-object heap. This is usually inlined and is just a couple of instructions: it's much faster than malloc. When the freespace pointer bumps into the end of the new-object heap a minor collection is triggered. This sweeps through the heap and copies every object in the new-object heap that still has references into a longer-lived heap. Your temporary string objects don't have any more references so they're skipped over and don't get copied. In other words, the overhead is based on the number of objects that do survive, not the number of orphaned objects.
It's a good idea to catch up on the state of the art before starting to describe what's wrong. You'd probably laugh at me if I started to talk about my ideas on how to make polygon rendering faster, just like you laughed at that co-worker of yours who was sure he knew all about how much it cost to manufacture iPods. =)
Isn't that kind of true for *all* memory-management strategies? Object-pooling isn't exactly unique to reference counting.
Again, this statement could easily apply to any of the other strategies, including pure tag-and-sweep.
It might be naive of me to think this, but uh, wouldn't the compiler be able to handle string concatenation more directly than that anyway? It seems odd that the + operator would simply be syntactic sugar for a large number of deeply-nested operations. It'd make much more sense for it to take a shortcut and just grab the internal data buffer. Though I guess then there'd be all sorts of fun edge cases with explicitly-created temporaries or whatever.
Then to me, that means the Java library is impressively inefficient.
Ah, okay... that's a pretty nifty optimization there, and would totally remove the "temporaries last until the heap totally fills up" issue that I thought there was. I didn't realize that there was a local heap.
Heh, I thought I *was* caught up. The NMSU CS department wasn't terribly strong in the whole systems programming side of things, though... lots of handwaving when it came to talking about memory management in anything which wasn't C, and not much discussion of libc either.
In a server app, the CPU is generally loaded, so you want to reduce raw cycles. In a client app, the CPU is generally mostly idle, so it is much more important to prevent itermittent long delays than it is to reduce CPU usage overall. In a standard Windows app, a memory allocation scheme that freezes the app for half a second every minute is much worse than a memory allocation scheme that requires ten seconds of CPU time each minute, spread out in evenly spaced ten millisecond calls.
Also, the most annoying about using JBuilder as the IDE is that, being written in Java itself, it'll be pretty snappy for 5 minutes but then suddenly decide to take 30 seconds to garbage collect.
"+" on strings is syntactic sugar for creating a StringBuffer, calling append on it, and then converting it to a String. You have to use a StringBuffer because Strings are immutable (which is good for a number of reasons, but bad here.)
You're probably as caught up as I am in most things
Anyway, yes, I would think that GC would be pretty bad for video games since real-time response is so important, and since everything is so CPU-bound anyway. But I guess no one asked me, or you
http://www.cuj.com/documents/s=8188/cuj0410i/
(It's probably too "fat" a technique for fluffy though...
(rasm fasm too much beer...brain cells...dying...)
'course, Java is kinda nuts about what it puts into separate threads by default, but I'm avoiding things like timers anyway (if only because having the Game object just call .repaint on the canvas is more efficient and so on).
beer == cooler. If I weren't stuck with an annoying cold *snork* today, I'd like to be unlocking and ref-counting that six-pack of Acme California Pale Ale in the fridge.
And I apologize for dead-ending into CS trivia. That's not what I mostly like to spend my precious blogging/journaling time on. =)
Unfortunately, all I have right now is cheap Mexican beer, and I'm out of limes. (Cheap Mexican beer + limes = awesome. Cheap Mexican beer without limes = the suck.)
On the other hand, Vanilla Coke + blue curacao tastes like rum and coke with an aftertaste of Creamsicle.
But oh well. At least we get to run native code...
Sure, rub it in.