Pointers and qualifiers

I had forgotten what the rules for pointer qualifiers were, so for the ignorant and forgetful, here they are:

The stuff to the left of the * is what the pointer points at.
The stuff to the right of the * is the qualifiers on the pointer itself.

So... volatile char* volatile * const ptr

is... a pointer that can't be changed, that points to a volatile pointer that points to volatile chars

 

Woo!

Benchmark, benchmark, benchmark

I've been meaning to add a yield() function to the SDL API for a while.  I've also been mulling around with different ideas to improve the spinlocks.

Here's the current spinlock (pseudo-code):
while (locked) delay(0)

My theory was that if the lock was contended, it's better to retry a few times before sleeping.  I also figured using the OS's thread yield function was a better way of giving up the current timeslice than sleeping for 0 time.

Here was my new spinlock:
if (!locked) return
while (true)
    for (i = 0; i < 4; ++i)
       if (!locked) return
    yield()

Astonishingly, my FIFO benchmark went from 3 seconds to 10 seconds!

Thinking about this a little, it makes sense... the CPU probably doesn't see the value change in as few cycles as the loop is, so all we're really doing is wasting time in the loop.  When there's high contention, as in my FIFO test, this just means the whole system is working harder.

So, I went back to my basic spinlock, but I used a yield instead of delay(0):
while (locked) yield()

Oddly enough, my FIFO benchmark wasn't any faster, in fact it was 4 seconds instead of the original 3 seconds.  Apparently on Mac OS X sched_yield() is a more expensive function than nanosleep().

My conclusion?
Always benchmark your changes, even if they're obviously an improvement, and don't be afraid to leave well enough alone. :)

Digitally Signing Documents

In the course of my business day, I frequently have to sign licensing or tax documents and e-mail them to people.

I've been looking for a paperless way to do this, and I've found a fairly easy way to do it using the GIMP (http://www.gimp.org) and OpenOffice (http://www.openoffice.org).

Setup:

1. Scan your actual signature and edit it in GIMP, converting the background to transparency using Colors -> Color to Alpha, and then save it as a PNG file.  You may need to rescale your signature to have it fit on documents, depending on the resolution of the original scan.
2. Download and install the OpenOffice PDF import extension: http://extensions.services.openoffice.org/project/pdfimport

Signing:

1. Open your PDF document in OpenOffice, which should open in the Draw program.
2. Select the Insert -> Picture -> From File... menu option and select your signature image.
3. Move it into place on the document.
4. Print the document and in the Print menu, select "Save as PDF"
5. Send it via e-mail!

There's also a really good digital signing service at DocuSign (http://www.docusign.com), and we'll probably start using that once there's enough volume to make it worthwhile.

Is Lock-Free worth it?

I've spent a bunch of time the past few weeks learning about lock-free and wait-free algorithms for super fast multi-threaded data structure access.

I've had two motivations for this.  First, I wanted to vet the new SDL atomic API, and second I wanted to potentially increase the performance of the SDL event system.

In the course of learning about lockless programming, I've gained a healthy respect for people who are doing it correctly.  It's incredibly tricky to get right, and even reviewed and published papers can have subtle bugs in them.  There are a lot of subtle issues and ways multi-threaded lockless code can fail, especially on the XBox 360 where data ordering between CPUs is not guaranteed at all without expensive sync instructions.

All of this has made me wonder if it's a good idea to make a cross-platform atomic API available in the first place.

But that said, let's first see what the benefits might be...

I wrote a lock-free FIFO that modeled the behavior of the SDL event queue, and created a test that could run both lock-free and using a mutex, to simulate the way the current SDL event queue is handled.  I then added a watcher thread and single spinlock to the lock-free version to simulate a thread periodically coming in and having to do heavy duty manipulation of the queue.

The test took 4 writer threads and had each of them put 1 MILLION events on the queue, and then created 4 reader threads to pull them off and process them.  The queue was limited to a maximum of 256 events.  I defined wait states for writers if they tried to add an event and the queue was full, and defined wait states for readers if they tried to get an event and the queue was empty.

I ran the test on a 4-core Mac Pro (with 8 hardware threads), on a mostly idle system.

The results were astonishing!

FIFO test---------------------------------------

Mode: Mutex
Finished in 37.097000 sec

Writer 0 wrote 1000000 events, had 0 waits
Writer 1 wrote 1000000 events, had 0 waits
Writer 2 wrote 1000000 events, had 0 waits
Writer 3 wrote 1000000 events, had 0 waits

Reader 0 read 999998 events, had 50 waits
Reader 1 read 1000003 events, had 23 waits
Reader 2 read 999998 events, had 13 waits
Reader 3 read 1000001 events, had 7 waits

FIFO test---------------------------------------

Mode: LockFree
Finished in 0.688000 sec

Writer 0 wrote 1000000 events, had 5308 waits
Writer 1 wrote 1000000 events, had 5263 waits
Writer 2 wrote 1000000 events, had 5348 waits
Writer 3 wrote 1000000 events, had 5314 waits

Reader 0 read 1023604 events, had 7838 waits
Reader 1 read 991976 events, had 7688 waits
Reader 2 read 981770 events, had 7700 waits
Reader 3 read 1002650 events, had 7893 waits

As you can see, the lock-free version was over 50 times faster than the mutex version!

On the other hand, the mutex protected queue was able to process an event in 9 microseconds, which is well within the design specs for the SDL event queue. :)

In conclusion, lock-free algorithms are a huge benefit for code that needs to be extremely high performance and scale well across many processors.  Applications of this might be fast transaction network servers, databases, or massively parallel data processing.

Resources:
http://msdn.microsoft.com/en-us/library/ee418650%28v=vs.85%29.aspx
http://www.1024cores.net/home/lock-free-algorithms
http://www.drdobbs.com/high-performance-computing/212201163

Oh, and if you're not afraid yet, think about might what happen if you're managing dynamically allocated objects with an atomic reference count...
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
http://www.drdobbs.com/architecture-and-design/184401888

Weekends are important!

This past week was the first week in a three week sprint I'm on to get SDL in a releasable state.  Realistically I know there will be some bigger tasks that will still need to be done, but I feel like I'll have most of the important smaller tasks and bugs and polish taken care of.  However there's a huge amount of work to be done, and to hit this goal I've been working almost non-stop for the past week.

Ahhh, weekend!

The weekend is hugely important, and I'm planning to take my weekends as family and planning time.  They give me a chance to slow down, relax, smile, and get perspective.  If I'm going so fast that I don't have time to relax on the weekend, I'm doing something fundamentally wrong and need to rethink things.

Ahhhhh. :)

/goes to hug his wife...

Multiple Gmail accounts

I finished setting up Galaxy Gameworks with Google mail and apps services today, and was immediately frustrated by the inability to have my business e-mail and my personal e-mail open at the same time.

I did a little digging and found that Google has indeed made it possible to have Gmail and the core web apps open on two different accounts.  However, setting it up is a little tricky.

You can turn on this feature by going to Settings -> Accounts -> Google Account settings, and then editing the “Multiple sign-in” setting.  Once you have done this and refreshed your browser, you can click the downward arrow next to your account name in the upper right and log in with another gmail account.

Voila! :)

Keeping the "Simple" in Simple DirectMedia Layer

SDL serves three types of video API users:

1. People who just want a framebuffer and use SDL 1.2 blit and direct pixel access to do the job.
2. People who just want an OpenGL context, and use OpenGL or OpenGL ES to do the job.
3. People who want a hardware accelerated 2D API

For 1 and 2, the functionality was available in SDL 1.2 and the feature set is well understood.

For 3, this is a new area that SDL 1.3 is supporting, and it's really easy to lose the "Simple" in "Simple DirectMedia Layer"

So I think here is a good time to remember that the goal of the SDL rendering API is simply:

Hardware accelerate operations that were typically done with the SDL 1.2 API.

This is tricky, since people did lots of interesting things with direct framebuffer access, but let me break it down into a feature set:

• copying images
• filling rectangles
• drawing single pixel lines
• drawing single pixel points

SDL 1.2 provided colorkey, alpha channels, and per-surface alpha, as well as nearest pixel scaling.

Again, to break that down into a feature set:

• blending for all operations
• single vertex alpha for all operations
• single vertex color for all operations
• scaling for image copy operations

It's tempting to add functionality here, but that road lies madness...

Organization is key!

As I'm starting to grow Galaxy Gameworks as a business, I'm finding that there are so many things to think about and keep track of that it's easy to feel overwhelmed.  I understand now why executives have personal assistants - they are essentially extra brains to handle all the myriad details involved in the daily business.

I don't have a personal assistant (my wife offered to help, but she's starting a business of her own and needs her own personal assistant!) but I do have a computer.  A computer is only as useful as you make it though.  You know the old saying, "Garbage In, Garbage Out".  I used to work for the government in Sacramento doing system admin and desktop support long ago, and I met many high level executives who had a computer and no idea how to use it.  Fortunately, I am computer savvy and can make my computer my b.. er, personal assistant. :)

Most of my communication is done through e-mail - licensing, bug reports, employee coordination, TODO notes to myself, social events, etc.  Up until now I haven't had time to organize my e-mail, so I just have a giant pile of messages where things easily get lost or left to sit forever.

This is bad.  Not only does it mean that important things are left untended to, but that I always have a low level of stress about not getting everything that I need to do done.  Worse, it means I don't even know what those things are, so I can't compartmentalize them and know that I'll get to them later.

So here are my goals:

• Respond in a timely fashion to people
• Know what needs to be done
• Know when things need to be done
• Make sure that everything has been addressed, either by trashing it or replying to it or prioritizing it on a TODO list.
• Feel good because I'm organized and responsible. 

People are important.  They tend to view their importance to you directly in proportion to your responsiveness.  If you respond quickly, you look professional and caring.  You can develop good relationships and get help with what you're doing.  If you don't respond, you often look like a jerk and people will look elsewhere for friendship or business.

Organization is important.  There's always more to do than time to do it in, and the only way you can find out what the important things are and prioritize them is if you have a good understanding of what all needs to be done.  In my case, I can only guarantee that I've handled and organized everything if I keep my inbox clear.

So I know what I want to do, but how do I get there?

Gmail to the rescue!

Gmail has a really powerful message labeling feature.  I spent a good amount of time this morning creating a set of labels that are intuitive and really helpful.  With too many labels I can't remember what label things go in or how I'm going to handle it.  With too few labels then things get clumped together and I don't get any organizational benefit.  Labels can have "/" in them and I use that to do logical groupings, which conveniently turn into folders on my iPhone mail program.  I also set up some message filtering rules to automatically add labels to certain types of messages, optionally bypassing my inbox entirely!

Gmail also has the ability to show and hide different labels in the sidebar, and I used that to keep categories of mail that bypass my inbox or that I need to deal with frequently available at a glance.

Gmail also has a "star" flag, which I use to mark messages for followup.  I can then click a link to bring up all my starred messages, and they show up in a list, along with their labels so I can quickly go through them and address them.

Finally, Gmail comes with a little task list.  I haven't used that much yet, but I'll give it a little spin and see if it's useful.

All of this organization takes some time up front, but the payoff is that I know what needs to be done, can do it more efficiently, and have peace of mind at the end of the day.

Suggestions welcome! :)

Learning is fun!

One of the things that's really fun about developing SDL is the incredible breadth of things that you learn in the process.

• A couple weeks ago I went from knowing nothing about Android development to being very comfortable with activity life cycles and JNI.
• Last week I dove into the dragon infested waters of atomic operations and lock free programming, and in the process was humbled and gained a healthy respect for people who do that for a living.  
• This morning I knew that CSS was used to affect the look and feel of web pages.  By the end of the day I had practical lessons on how it works and affects the style and behavior of a site.

I wonder what I'm going to learn tomorrow .... ? :)

Making website feedback easy

The last few days I've been working with my wonderful documentation guru, Sheena, to streamline the process of creating and contributing to SDL documentation.  We needed a way for people who want to contribute to the documentation effort to share information and coordinate their efforts.  We also wanted to make it extremely easy for people using the documentation to suggest improvements or request clarification.  We're using a wiki, but have locked down permissions to avoid the plague of spammers that abound on the Internet today.

Creating a way for active contributors to coordinate was easy.  We're hosted on Dreamhost, and they make it painless to set up a new mailing list, so we redirected docs@libsdl.org to a new mailing list for contributors.

Creating a way for casual readers to contribute and give feedback was more difficult, especially since I wanted to make giving feedback inviting but not require Sheena to add markup to each page.  I wanted to make it possible to give feedback without following a link to another page, so the person would have the context of the page they were on for giving great feedback.  I also wanted to make sure that it was obvious how to give feedback, but also didn't interfere with the page content.

With these requirements in mind, I set off in search of the perfect feedback system!  After a short search, I found something that looked pretty promising:
http://tutorialzine.com/2010/09/quick-feedback-form-php-jquery/

It was pretty much self contained, which was a plus in terms of integrating it into the wiki site, and did a good job at being accessible without keeping an entire form on screen.  However once we added it to one of the wiki pages, a few problems became immediately apparent.  First, the color and general style didn't match that of the documentation site.  That's not too bad, a little photoshop time and adjusting some of the CSS sizes and offsets, and we're done.  A bigger problem was that it was positioned at the lower right, continually obscured important information on the page.  We looked at a couple of ideas, but the one that really made sense was to put it in the upper right.  A little looking at the CSS and Javascript code, adjusting some offsets and flipping the arrow toggle state, and we're done!

... or so I thought.

It worked perfectly in my test file on Firefox, but when I opened it in Internet Explorer it was complete garbage.  Not only was it not anchored in the upper right, but elements were badly overlapping and the button didn't animate anything.  To make matters worse, when I moved the feedback form from my test document to the real wiki page and viewed it in Firefox, the sliding panel was neatly anchored already out, instead of tucked up out of sight.

Okay, one problem at a time... first, what's the difference between the test file and the wiki page?  After putting some tests together and scrutinizing the page source, I realized that the wiki page had a <!DOCTYPE> element while my test page was hand coded HTML with no doctype.  It turns out that Firefox is smart and if a page specifies a certain flavor of markup in it's doctype, then it will be compliant to that standard.  If a page doesn't specify a doctype, then Firefox will enable quirk mode, which is essentially the combined experience of lots of web developers making pages work.  Now that I know that, it's just a matter of looking up the relevant section in the standard and fixing it right?

... of course not. :)

It turns out that the technique I was using, negative margin values, was perfectly acceptable and compliant.  After playing with it a bunch, I could never get the panel to move regardless of what margin values I used.  I shelved the problem and went back to Internet Explorer to see what I could do there.

<montage scene of me completely deconstructing the HTML and CSS and rebuilding it a piece at a time>

So after playing with it a lot, I realized that using headers and spans mixed with div markers was completely hosing Internet Explorer.  I carefully rebuilt the form using only <div> and images and after a few trials, voila!  It was anchored correctly, the sliding panel was initially out of sight, and then popped down into the correct location when I clicked the arrow.  I quickly switched back to Firefox and Safari and they were happy as clams.

Now that I had a working feedback form, I had to figure out how to integrate it seamlessly into the MoinMoin wiki.  I poked through lots of python code for generating the sidebar and implementing themes and found that someone had thoughtfully created a way to add custom markup to the footer of each page.  I just set the variable "page_footer1" in wikiconfig.py to the feedback form markup, and the feedback form was now on each page of the wiki.

For the final touch, I wanted the feedback to go to the documentation mailing list and include which page the feedback was coming from.  A few quick edits of submit.php and we are off and running!

You can see the final result in action at http://wiki.libsdl.org, and the code is available for your perusal at http://wiki.libsdl.org/feedback  Feel free to use it however you like, and let me know if you find a way to improve it!

Welcome!

Welcome!

I'm working full time on Simple DirectMedia Layer now, and in the process I'm learning so much about lots of new topics.  I've been really impressed at how much good information I've found on people's blogs, so I thought I'd start one and both show my ignorance and help others who are following in my footsteps.

Cheers! :)