Rakkar's Blog

A few years ago, a user in the forum stated that UDT had much higher throughput than RakNet for LAN transfers. I took a look at it and it was made by a couple of research scientists for the purpose of being faster than TCP. While they published details of their work, the documentation is extremely technical and academic. Anyway, I said at the time that RakNet was designed with different goals, and if all they wanted was high speed LAN transfer to use UDT instead.

Since that time, I had ongoing problems with congestion control. Every 2-6 months I’d try a different approach with incremental improvements. But with the wide range of scenarios under which RakNet is used, there was always a new scenario where it didn’t work. So I basically gave up, and turned to UDT for help.

My first approach was to directly integrate UDT into RakNet. I spent about a week removing all exceptions from the UDT source, changing to the RakNet memory allocator, and integrating RakNet to use UDT for sends and receives through RakNet’s own sockets. I had it working, but had problems where UDT didn’t connect as fast as RakNet. UDT also didn’t support priority levels or different sending types other than RELIABLE_ORDERED. I wasn’t happy about having another UDP library integrated into my core product just for one feature (congestion control). In the end, I released this an optional define flag. It’s present in version 3.62 though I left it disabled by default.

At random, I saw an advertisement by one of the authors of UDT, Yunhong Gu, for paid contracting. Rather than have him code a solution, I had him write a technical design document on how the UDT congestion control was implemented, so I could implement it myself.

The result of my implementation

Using DevPartner performance analysis I eliminated the top 20% CPU utilization from RakNet. I also reduced the bandwidth overhead, even though more information is sent. In the end, I raised the file transfer rate on localhost from 2 to over 20 megabytes per second (I’ve seen it go as high as 40 on another computer). And the transfer rate to my remote server went up by 50%.

I’m pretty happy with the end-result. This is probably the most significant improvement to RakNet I’ve made since it was developed. I’ll be releasing this as version 3.7 in the very near future.

I have a B+ tree containing pointers, sorted by key. I had a queue which mirrored that tree, but was ordered by a fixed-interval timestamp (from most recent to least recent). I recently encountered a situation where I was able to look up the pointer by the key in the B+ tree, but didn’t know its index into the queue. Since the queue could be tens of thousands of elements long, and the same op. had to be repeated many times, it was too slow to stick with. So I changed to a linked list. That way I could remove from the middle of the queue and readd at the head of the queue without scanning the queue for its index.

I’ve been using a function object design pattern for my Lobby system and it’s working well enough that I wanted to post about it.

The concept is very simple. Encapsulate the input and output parameters to a function, and the function call itself, in an object. This lets you manipulate a function call the same way you do objects.

Some useful things you can then do:

1. Serialize them over the network
2. Save them to disk
3. Put them in a queue, for a test execution path
4. Save them to call later
5. Move the inputs and outputs around between threads
6. Log what runs
7. Perform operations on a set of function objects via the base class
8. Give the user more functions by giving them more function objects from a class factory, making the system easy to extend.

So the lobby system exposes a large set of function objects. The user gets one from the class factory, with an identifier for what function to perform. The input parameters are filled in. They are serialized, processed remotely, and sent back. The user has all the contextual information because the input parameters are sent back as well as the output parameters. And a cool thing about this is the memory for function call lives on the internet. From the client’s point of view it is stateless. The client doesn’t have to track what is running.

It’s also useful for asynchronous operations.

In my case, rather than having a function pointer, the functor’s operation is in the functor itself (e.g. DoWork()). The needed parameters are passed to DoWork(), and operate on the database.

It’s interesting, even to myself, how contracting has changed my perceptions of labor over the last few years.

When I started contracting, I didn’t act any differently from the employee I was used to being the prior years of my career. I generally came in the same hours, spoke to the same people, attended the same meetings, and did similar tasks. However, there was a seed in the back of my mind that I was now working for myself and the company was a customer. A crucial difference, now being able to say “Why would I go to the company party? I don’t work here.” It’s like when you meet your boss for the first time in the interview, and he’s just a normal guy like any other. Eventually that feeling turns to “my boss” but if you’re a contractor it’s “my customer” and he’s still just a normal guy.

It’s become a strange concept to me that a company can control your comings and going. I know it happens because I see it happen to others, and I remember it happening to me when I was an employee. I used to have boring days where I would sit there and watch the clock until I could go home. That thought now evokes images of outrage, and slavery. How can someone else tell you, a human being, where you can and can’t go, or when you can do it? I used to complain that I’d have to sit there if I had nothing to do. Now, it’s my own time. Once my customer is happy with my progress, I go do something else. Sometimes work for another customer. Sometimes I keep working for them, but at my own office.

There is no longer a line between work and home. My job for the client is to ensure they are happy with the services I provide so they continue to be a customer. I don’t complain about working nights or weekends if I need to, because all the time is my own to begin with. Time is not relevant, only the assigned work is.

Similarly, there’s no issue of doing the minimum work to get by, because I’m not working for someone else directly. I’m providing a customer with a service, and of course when running my own company I will do the best job possible.

I could never go back to being an employee. The feeling of freedom working for yourself is like the feeling of being alive.

Here’s some random tips to help out other contractors or potential contractors.

1. The employer will act outraged, shocked, and/or feign ignorance of the various costs and taxes when they hear your price. But it’s just a negotiating tactic to pay you less. Knowing the facts, showing you know them, and not backing down directly equates to more money
http://www.rakkar.org/ContractPayCalculator.html

2. Not all employers understand the laws or differences between contractors and employees. When I first started contracting I thought of the differences in terms of the law, but now I just think of the differences in what I am willing to work for a customer.

For example, if the company insists that you be there certain hours although you have nothing to do that day, you can say “My monthly fee is for roughly a month of tasks. While I don’t charge less for months where I have less to do, neither do I charge more when I have more to do. I’m happy to stay, but I’ll be billing hourly and this will cost you more in the long run, especially during crunch time.”

3. If helps if you make so much money or are in so much demand that you don’t need a particular customer or job, and are therefore able to drive harder bargains and set your own terms. Having your own business makes much more money than being an employee, and after a few years you tend to reach this point.

4. Flying around the country invokes a very real time and cost to you, that is hidden to the customer. A two hour flight takes three or four hours each way when you count check-in and the drive to the airport. At the end of the day you’re probably not going to be doing much other than watching TV in a hotel. And you get nothing for the unpleasantness of sitting in an airplane.

Jobs where I didn’t charge for this time made me unhappy in retrospect, four days of effort for two days of pay. However, jobs where I did charge (a discounted rate) for this time made the customer unhappy, especially as I didn’t charge for that time previously. I can see their viewpoint – you are charging more than they make themselves just to sit on a plane and do nothing useful for them. The approach I’ve taken now is to just bill more for short-term contracts. Although, even at the rates I charge ($125 an hour) it still isn’t worth my time or effort financially. I think of it as a necessary support effort I provide for licensing fees I’ve already made, rather than a source of income.

I took the demo for the game engine Irrlicht and added multiplayer to it in two days.

Download

Technical details

I have to say again that Irrlicht is a great engine. Very easy to use, very well documented. I had to go to the source a few times but it was nothing major.

I was thinking lately what a good market middleware is

• Write once, sell many times
• Focusing on a specialty lets you beat out companies that do that one thing incidentally
• Even as an individual with no marketing, you can outperform large companies that spend 100x what you do

And thinking to take that to the next step, with a game engine. I’ve noticed that game engines get many times the attention of individual libraries, much more so than the sum of their components. Imagine a game engine where each component is a specialized best-of-class library. RakNet times 7, the other 6 being graphics, physics, audio, AI, UI, and tools. If I knew 6 other developers or small companies that had the same quality as RakNet, at a similar price, it would be a great venture to join forces and make an engine as the integrated sum of those libraries. Such an engine would dominate the market immediately in terms of quality, because no existing monolithic engine, no matter how good, could beat a specialized company that focuses on that a single aspect. If you were to take all these specialized companies together then, all other engines would be fail because none of them could compete in any area.

It’s sort of like how you can take any default Windows application and find a better substitute on the net. It’s not that Microsoft did a bad job, but that their focus was on an operating system. Specialized companies turn around, find a niche market for that application, and beat Microsoft because that is their core focus. If you’re not going to do a way better job then there’s no point in entering the market.

If these libraries could be integrated seamlessly, with the full feature set for each library exposed, it would like astounding.

I’m revisiting Irrlicht to add multiplayer to one of their demos. It’s a fantastically easy to use engine that is well-written and well-documented. A few years ago I didn’t use it for Galactic Melee because of lack of tool integration support. Hopefully it’s better on that now, although Ogre didn’t turn out to be that well-integrated into tools either in hindsight.

I’ve been working with the owner of a new engine lately. It’s an interesting scenario: He paid a programmer to write an engine for him apparently on a contract basis. The programmer did so and went on his way. Then he then hired some artists to make content. That was done. He is now trying to sell the engine, and I took a look at it to see about integrating RakNet.

A concise summary is “Promising but won’t save you time”. Promising in that there are many libraries to do many different things, and with a few script calls you can get a lot done. Won’t save you time in that it is undocumented, complex, heavily specialized for a particular type of game, and uses macros and cast-from-void-pointer hacks to avoid having to write interfaces.

I read a similar complaint in the forums

User: “How do we do this?”
Owner: “Look at the source”
User: “The library is closed source. It is impossible to do anything”
Owner: “It is possible, you just have to figure it out.”

The reason for that is the owner is not a programmer, and doesn’t want to pay a programmer for general forum support.

So I brought this to his attention

Me: “If you want to succeed, you need to document your stuff. I can’t figure out how to do anything. Other people who buy it aren’t going to be able to use it, and will be pissed off.”
Owner: “The programmer said experienced users don’t need documentation. They just look at the source.”
Me: “It is closed source. The programmer is saying that because documentation is not fun to write.”
Owner: “I don’t want to pay for documentation. If we’re successful, it’ll have documentation at some point.”

Hopefully things come through for them, but I doubt it will.

I wrote DS_Multilist.h. It’s an unordered list, stack, queue, and ordered list all in one. Since the interface is the same for all 4, it’s easy to change what type of data structure you are using to tweak performance. Relatively full featured, with a sort function and fast lookups into sorted lists.

Multilist

Here’s a class that given a predefined area of memory, allows you to allocate and deallocate areas of that memory. In other words, a custom memory manager.

Only partially done yet, but it’s already 25% or so faster than malloc and free
Header
CPP

Full alloc, then dealloc
Heap = 1304 us
malloc = 878256 us

Fragmentation
Heap = 3525 us
malloc = 4462 us

Most of the speedup comes from linked lists of buckets. There are 7 buckets, from 32 bytes to 2048 bytes, incrementing in powers of two. 20% of the given memory is dedicated to buckets. If an allocation is requested and a bucket is available, the allocation goes to that bucket instead. Because buckets are contiguous and reserved, those allocations cannot cause fragmentation.

The alignment boundary is 32 bytes, so all allocations returned to the user are aligned, and the average memory wasted per allocation is 32 bytes, excluding buckets.

The speeds shown are with a critical section lock. This is not necessary, and for single threads it would be even faster.