27
Oct
14

A Guide to Memory/Object Pooling

I was recently listening to a vlog by a games developer who wanted a new programming language specifically for games, and one of his big gripes with C++ was the memory allocation process. He had a number of arguments, none of which resonated with me, but it did spark interest for me in the memory allocation/de-allocation problem. I’ll briefly discuss the problem from the perspective of a language like C (in this case Pascal) and one that uses garbage collection (in this case Java).

Most languages dynamically allocate and free memory in very much the same way as even very old languages such as Pascal did. You have to explicitly ask the API to allocate memory for you, and then explicitly free it when you are finished with it. In an OO language like C++ this results in the need for destructors to free the memory the object uses when it is destroyed.

Either way memory is allocated and freed, and if it is done on a regular basis this can lead to something called heap fragmentation. Heap fragmentation is not quite the same as disk fragmentation in that an allocated block will not be split up. Pascal for instance allocates memory one block after another, simply creating the new one at the end of the old one. However when a block of memory is freed it leaves a hole, these holes are effectively heap fragmentation.

Pascal deals with these holes by maintaining a free list, which is a linked list containing all the free blocks available. When an application allocates more memory the list is traversed to find the first available memory big enough for the new allocation, hopefully filling the hole but possibly leaving a small amount still available. Clearly the holes will likely get smaller over time until they are unusable, and the more holes there are the longer any memory allocation will take.

Other allocation schemes are available in other languages, but they have similar issues, take a look here to see what I mean. Whatever scheme you use there is significant cost the more you allocate and free memory.

Garbage collected languages such as Java have problems of their own. Whilst it is claimed that allocating memory in Java is practically free in terms of complexity, freeing memory is known to have performance issues as the garbage collector (GC for short) kicks in to clean up. The mechanics of the memory allocation mechanism are largely hidden in a language like Java, so that shouldn’t concern you much, but the performance impact a garbage collector can have should concern you.

So why is the GC a potential performance hazard? In order for the GC to know which memory to free it must work out which memory is still being used. One way of doing that is maintaining a reference count for each pointer/reference in use. Obviously any reference with a count of zero can be freed, but this leads to another problem, determining which collections of objects can be freed.

Imagine a data structure like a tree in which every node holds a reference not only to its children but its parent as well. If you were to use the tree, holding only a reference to the root node, then later released that reference, reference counting would not enable freeing the memory the tree uses. Even though no external objects can reach it. A GC therefore also needs to have an algorithm that will check the reachability of memory.

That’s a rather simplistic view of garbage collection, but it’s enough to see that running the GC can be expensive.

So how can you deal with these issues? It seems it doesn’t matter which kind of system/language you use, memory management has real implications for performance. One answer is to use a technique commonly called object or memory pooling.

A simple way to think of a memory pool is that it’s a lot like a cupboard. When you need something it’s quite quick to go to the cupboard and get something that’s available there, and when you’re done with it you return it. If the cupboard turned out to be empty, you’d have to go down to the shops in order to buy more of whatever you need. An advantage being you can stock your cupboard with resources you plan on using later.

Memory and object pools are effectively exactly the same thing. You can preallocate memory, use it, return it to the pool, then use it again. This reduces the amount of stress on the memory allocation system, leading to fewer GCs and less heap fragmentation. You’d be amazed how much difference something like this can make on a system, especially something like Android.

As an example, I implemented a path finding algorithm in Java for a maze game I am writing. I could have used a dynamically sized data stack that grows and shrinks as the algorithm functions. That would however trigger the GC much more frequently as is uses and releases memory on the data stack. It is much better to preallocate the maximum size of the stack once, and reuse the same memory every time the algorithm is used. This only allows one instance of the algorithm to run at once, but it can be adjusted to allow multi-threading by creating a shared pool that each instance can use.

So what kinds of objects or memory should you use pooling for? Ideally anything that is short-lived should have some kind of pooling scheme in place as they put the most stress on the memory allocation system. This would be objects like particles and bullets in a game engine. Long-lived and infrequently used objects that pose less of a problem to the system don’t really need to be pooled as they cause much less stress.

Pooling can also be used for other resources that are expensive to create and destroy such as database or network connections. This can help alleviate stress on other systems such as the network stack, database servers, and file systems. So they are really an import tool in any programmers toolbox to improve performance.

20
Oct
14

3rd Aniversary and Work on the Sparcstation

This weekend marks the third year I’ve been writing this blog. The first thing I wrote about was my Sparcstation 20, which I had just acquired at the time. I installed NetBSD 4.01 on it, which was reasonable then, but has become quite out of date now. So 186 posts and 3 years later I’m in the process of upgrading the machine to NetBSD 6.1.5.

Machine without the PSU

Machine without the PSU

This has been a long time coming, and there are a number of reasons for the upgrade. Firstly, the older version of NetBSD was becoming more difficult to keep software up to date on. I had stuck with 4.01 for some time because of performance issues I had when trying out 6.1.2 last year. But some packages didn’t update properly lately and I had been left with some software working and others just becoming broken. I could have stuck with an older version of pkgsrc, but that has problems as well.

Another reason is I’ve received the hardware required to use the machine as a desktop machine with screen,keyboard and mouse instead of a headless server. I retired the machine from active server duty and built a replacement server quite recently to facilitate both upgrading the OS and hardware to try and make it a practical desktop workstation. I was very fortunate to receive a donation of a keyboard and mouse suitable for the machine, and have since bought the frame buffer card and adapter to complete the hardware necessary.

Frame Buffer

Frame Buffer

I got the hardware up and running last weekend and powered up the machine with everything set up for the first time. I was happy that without upgrading the OS, I had the display, keyboard and mouse all working with an X server with little effort. I was impressed that the X server seemed quite speedy compared to what I expected. However X server (Xsun) was really outdated and didn’t seem to support everything thrown at it.

So I began to install NetBSD 6.1.4. I found it was best to use the serial console for the install as the install disk does not handle the sun console on the frame buffer properly. It seems that it just doesn’t have the TERMCAP entries for the sun console, as once the system is installed the console works fine. The install worked pretty much the same as the older version with a few minor changes. The performance of 6.1.4 seemed better than the last time I tried an upgrade, but still isn’t as fast as the older 4.01 release.

So I’ve begun building the system from sources to take advantage of the V8 Supersparc. I’m assuming the binary distributions you download are actually built for the slower V7 Sparc that can be common in some of the other older and slower machines. The build process is surprisingly very easy to follow. We will see if there is any significant difference when it’s finished building.

 

14
Oct
14

Works for DOS

Goughlui has recently had an interesting look at some old versions of common productivity software, namely Power Point and Lotus 1-2-3. I thought I might contribute by documenting some of the old DOS productivity software that I have, and today I’ll be looking back at MS Works 2.0. There’s a lot to look at so this might take a while!

This version of works was developed back in 1987-89, but my Dad didn’t buy it until some time later in the early 1990’s. We used it for pretty much everything. Me and my brothers wrote much of our homework on it, and Dad used the spreadsheet to manage the farms finances.

It wasn’t the first office suite we had, but it was used for most of the life of the old DOS PC.

You’ll notice from the screen shots that works primarily uses ASCII characters in place of graphics. It does however have a graphics mode to display the text allowing bold, underlined, strikethrough, and italicized text to appear on screen. Most other word processors used colours or special characters to indicate these features and were consequently much harder to read.

I have had to capture most screenshots in a basic text mode as dosbox doesn’t emulate the graphics mode works uses very well. This results in some parts of the screen not updating correctly when using the graphics mode in dosbox.

This version of works includes 4 major functions. A word processor, spreadsheet, database and communications package. I’ll try to talk about each in turn.

Graphics mode

Graphics mode

Text mode

Text mode

Firstly the word processor. It would be considered fairly basic by today’s standards but had a very good feature set for the day. It does most things modern word processors do with a few exceptions. Whilst there are formatting options such as bold and double spacing, there are only a limited set of fonts and text sizes available. Fonts and sizes depended on the printer support installed and didn’t change the appearance on screen.

Also inserting any kind of graphics is limited to charts created with the spreadsheet. Like Goughlui I’ve constructed an animated GIF with the menus to give you an idea what the word processor can do.

The spreadsheet is similarly limited. You can’t add graphics and formatting text is limited. It is however very usable for most basic tasks. Something that would frustrate many users is the lack of easy to find help when typing in formulae. It also lacks the feature of having multiple work sheets in each spreadsheet file.

You can create a chart based on data in your spreadsheet, but again the features available are limited in comparison to modern software. It does however manage to offer a number of different chart types such as the normal bar, pie and x-y charts.

Again another GIF of the menus available.

Works includes a very basic flat-file style database, but it is of very limited use because most things could be done much easier in a spreadsheet. The main reason you may use the database would be if you intended to use the mail-merge feature as using a spreadsheet file is not supported.

Database software like this hasn’t really survived today, as software like MS Access seems to be absent from current office suites.

Works includes a basic communication package which is basically a VT52 or ANSI terminal emulator. It does support sending and receiving files, but it seems that it doesn’t tell you which transfer protocol it uses. It probably would have been adequate to connect and upload/download files to or from a mainframe or mini computer, then still a common part of corporate infrastructure.

Finally something I remember playing with and enjoying as a child is the tutorial program. It is a whimsical introduction to the software for absolute beginners which actually does a pretty good job of teaching the basics of using the computer and works itself. The program shows you how to do something and then guides you through doing it yourself.

It reminds me of the IBM PC demonstration disk that Terry Stewart showed on youtube for his machine. You don’t see tutorial programs like these any more!

Compared to modern software Works lacks much of the features we take for granted today. However I have found that it is still quite usable today, as long as you don’t need graphics of any kind. I wrote today’s post using its word processor and found that the basic editing is as good as modern software. Mostly it’s missing features that DOS machines of the late 80’s and early 90’s weren’t capable of without a GUI like windows to support the application.

06
Oct
14

Boppin’ for DOS

Boppin’ is a puzzle game developed by Accursed Toys and published by Apogee in 1994. Unlike most puzzle games this one has a story, you play as either Yeet or Boik in a quest to restore all the bad guys to the video game world that were stolen by Hunnybunz. Without the bad guys all the heroes are out of jobs and are bored as no-one wants to play a game that isn’t complete.

It was originally made for the Amiga, but it didn’t see much success there. So the authors ported it to the PC and made some improvements and trade-offs in the process. The PC graphics in VGA were re-mastered in 256 colours as opposed to the 32 used on the Amiga. The sound however had a down-step in quality on the PC as it was converted for lower bit rates and FM synthesis.

The VGA graphics are excellent, they are very artistic and unique for games of the time. This is hardly surprising as one of the designers had lots of experience with artwork and designing tiles and sprites for games. I was also impressed in general with the animations, although you need a machine better than the minimum specs to avoid slow down. The minimum specs call for a 386 with 2MB of RAM, I’d suggest a fast 386 at a minimum and to avoid any 386sx machines as they have limited memory bandwidth. This would have made the game less popular with owners of older machines at the time.

Something interesting you may run into depending on the version you play is the suicide animations for Yeet and Boik, and the ‘Deaddy bear’ logo for Accursed toys. These feel like strange additions to the game given the artwork and graphics are fairly cheery and colourful. It doesn’t fit with the motif of the game. The later version of the game had these removed by default with a ‘politically correct’ logo screen for the company and the option to re-enable the blood via the command line.

Sound support comes in many flavours including the Sound Blaster, Gravis Ultrasound, Pro Audio Spectrum and more. I used Sound Blaster support as that was most convenient at the time. Digitised sound is used for the sound effects, and they were what you’d expect for the most part. The FM synthesized music was much more interesting and quirky, reflecting the art style and atmosphere of the game. Again, when playing on a slower machine the sound quality suffered much like the graphic speed, another reason to use a faster DOS machine.

Controlling Yeet (or was it Boik?) is fairly straight forward. You can move either left or right with the usual keys and can use up and down to use elevators. You are meant to throw blocks around the play field so that they collide with like blocks to eliminate them. You throw a block by holding the ‘waggle’ button and either left or right and then releasing the waggle button. This was a bit odd at first, but I got used to it. The blocks only travel in diagonal directions at first and will bounce around until they hit either a refractor which changes their direction or a block that will stop it either for elimination (known in-game as boppin’) or losing a life if the block doesn’t match or has hit a non-bouncy wall. It sounds more complicated than it actually is.

It was actually quite easy to learn enough to play through the earlier levels quite well. There is no time limit so it pays to carefully line up your shots and work out any bounces. If you do happen to get stuck in a level, you can restart it restoring your lives and score. If you happen to die, you can continue with the only penalty being loss of score. It makes progressing through the levels much easier and means you won’t have to repeat the earlier levels every time you die.

The game also includes a two player mode. Basically you both just compete for points by trying to bop the blocks faster than your opponent. It basically just adds the urgency that the single player game lacks. Unfortunately I didn’t have anyone to play with me to try it out properly.

In the end I found that it was quite fun, but it wasn’t as challenging as I would have liked as a single player. Once I had mastered the controls and got a feel for how the blocks move and bounce it got significantly easier, the main challenge remaining was learning the level layouts and the best way to complete them. There are lots of levels, and you can load and save your game, so you need not repeat playing any levels to preserve some of the challenge.

Boppin’ has been released as freeware and is fairly easy to find. If you go to the home page for the game you will find a windows version of the game that uses the Amiga sounds and music whilst retaining the DOS graphics and levels, getting the best of both worlds. The windows version also restores the original gory logo and the suicide animations, I wonder where they were trying to go with that?

26
Sep
14

A Tiny Hitachi Hard Disk

I was given this small Hitachi hard drive that I just had to photograph and share.

Here it is next to a standard sized 2.5 inch drive. Amazingly it is almost half the size of the full sized drive, and yet has 4 times the capacity. The drive was made in June 2004 and has the Travelstar name printed on it, indicating that this was likely an IBM model. Hitachi and IBMs hard drive division had merged in 2003, IBMs Travelstar and Deskstar series drives became a part of the Hitachi line. Even after the merger IBM continued to use the now Hitachi parts, this particular example came out of an IBM Thinkpad.

Unlike the IBM Deskstar, Hitachi drives have mostly had a pretty good reputation. I only every saw mostly 2.5 inch drives in the wild, usually in laptops.

Here is a shot of the underside of the drive, nothing really all that special to report. Until next time…

21
Sep
14

Restoring the Sun Keyboard and other Randomness

A few weeks ago I had a Sun type 5c keyboard and mouse donated to me by a co-worker. It is significant because it will allow me to convert my Sparcstation 20 into a desktop workstation. I have a sbus frame buffer card on order and just need to get a 13w3 to VGA converter to complete the machine. I had previously been using it as a server for VPN, HTTP and SVN duties.

Sun Keyboard and Mouse

Sun Keyboard and Mouse

Continue reading ‘Restoring the Sun Keyboard and other Randomness’

17
Sep
14

Captain Comic for DOS

Before 1990 the platform game genre existed almost exclusively on game consoles like the NES. It was thought that the PC didn’t have the capability to produce scrolling graphics quickly. This of course is debatable as the technology existed much earlier in the form of the 286 processor, EGA and VGA graphics cards. I’d argue that it could have been possible by around 1985-7, as the 286 had become more powerful, and the graphics cards of the time had the capability.

Today’s game, Captain Comic, was released in 1988, two years before Commander Keen and the rise of the platform game on the PC. It was created by an individual, Michael A. Denio and was self published under the shareware model. It has historical significance as the first side-scrolling platform game on the PC.

The game uses EGA graphics, which I think are designed well. The sprites are colourful, easy to identify, and animate nicely. The levels have unique backgrounds which give the context for the levels and are quite attractive. I thought the author had done quite a nice job with the pixel art in general.

comic_001Although playable and quite an achievement at the time, the engine doesn’t seem capable of either smooth scrolling or a higher frame rate. This is hardly surprising, smooth scrolling on EGA requires specialised knowledge of the cards registers and memory map and using them cleverly to reduce the drawing load on the card. Impressively there is absolutely no flicker, which was a common problem on consoles and many old PC games. I’m guessing he used EGA page flipping or a double buffer to achieve this.

The game supports PC speaker sound, which is fairly basic and is ok for what it is. The Adlib came out the same year, and as the game was made by one guy it’s understandable he didn’t include support for it. There weren’t any other sound devices he could have used.

I used the keyboard controls for playing and found they were pretty good. The only problem being that you can end up moving about half a tile more than you thought depending on when you released the key. I suspect this is because of the games lower frame rate, you could release the key during the screen redraw, but after you’ve actually moved. Otherwise the controls for movement and jumping are accurate and responsive.

The game itself is fun and challenging, and it isn’t overly punishing of mistakes. Enemies can hit you 7 times before you die, and they are destroyed when they make contact with you. Every Screen edge and door is effectively a check point as you return to the last one used when you die. The only thing that does punish you really is running out of lives, although you get extra lives if you pick up a shield when at full health or for every 50,000 points.

I didn’t get as far as I would have liked, but I found Captain Comic a charming, fun and challenging game. I didn’t get frustrated with it when I died, because it was usually my own fault. Each time I started again I got a little better, and a little further in. I even managed to find some of the items such as the cork screw and gems.

Unfortunately it wasn’t a commercial success when it was released, but it seems to be fondly remembered by others on the internet. I’m rather impressed with what was achieved by a single guy. Whilst not smooth scrolling, the graphics are technically impressive, the game play is solid and the levels are challenging and fun. If you have a chance and like old DOS games give it a go.

This slideshow requires JavaScript.




Blogs I Follow

Enter your email address to follow this blog and receive notifications of new posts by email.


Random Battles: my life long level grind

completing every RPG, ever.

Gough's Tech Zone

Reversing the mindless enslavement of humans by technology.

Retrocosm - Vintage & Retro Computing Blog

Random mutterings on retro computing, old technology, some new, plus any other stuff that interests me

ancientelectronics

retro computing and gaming plus a little more

Retrocomputing with 90's SPARC

21st-Century computing, the hard way

lazygamereviews

MS-DOS game reviews, retro ramblings and more...

Follow

Get every new post delivered to your Inbox.