Saya Video Editor unofficial dev blog

Slowly advancing...

2011-04-22T18:03:00.000-07:00

The resources panel has been redesigned, and now accepts Drag and Drop for quick importing of files. Multiple files can be imported on the same operation (that is, once I write the part for actually importing a file), and if accidentally you import 100 files, you're presented with a confirmation dialog.

In other news, I've decided to switch the project file format from XML to JSON. It's just much easier to handle.

Argh, there's so much to do, and I don't know where to start!

Status update

2010-11-22T20:00:00.000-08:00

Just wanted to tell you people that I'm still alive, and the project's getting a healthy recovery. It's still very weak, but I'm gaining pace and some functions that were forgotten are being implemented right now.

I hope to have a functional playback controller soon (still without codec support, unfortunately).

Read the official blog for more info.

Personal situations update: July 10, 2009

2009-07-10T17:01:00.000-07:00

Hello. Just wanted to update you and tell you that Saya is NOT dead... by an inch.

The depression came back, but this time I've really managed to overcome it. It has been a very chaotic month. I began to feel lonely and in desperate need to seek a girlfriend. My delusions had made me believe that I could never find a girlfriend (in part because of my own depression), but thanks to a huge effort involving courage, asking girls out through third parties and joining several social networking websites, my self-esteem has finally stabilized to a non-negligible positive value.

On the other hand, I got a job! And a very good one. Not very good financially speaking, but one without excessive stress and which will allow me to occasionally work SOHO (at home).

Today is one of those days. I got a terrible stomach sickness (I'll omit the gross details) today's morning, and I had to stay at home. Even with a huge pressure to have the work finished by this monday, I feel fine. I've also upgraded my copy of Code::Blocks (which now has a lot of very-needed features) allowing me to code without problems.

This is where things are getting interesting. The combination of programming seriously while listening to my favorite music at home, has given me a second boost in the desire to keep working on Saya.

Unfortunately, i have very little time left. But at least Saya is getting a ray of hope as an in-hiatus project. Don't despair!

Maybe in a couple of months, if everything goes well, I'll be able to get back to work on the project.

I'd also like to thank everyone for their kind words of support during my darkest hours. Thanks to you, and to everyone who prayed for me, I'm still alive, and kicking!

Thank you all!

Sincerely,
Rick.

P.S. Receiving some money would also help. If someone charitative wants to give a poor programmer some financial support, he's welcome to do so ;-)

The depression is over!

2009-06-07T11:22:00.000-07:00

NEW LIFE, HERE I COME!

A week ago I joined okcupid.com, an online dating site based on questionaires so that you can find your match based on politics, moral, hygiene, religion, common interests, sexual tastes, attitudes towards life and whatnot. Answering over 1000 multiple-choice questions has helped me know myself and boost my self-esteem. I no longer feel lonely or doomed to die abandoned by everyone. I go to bed with hope instead of pain, and wake up with joy instead of the burden of having to live another day.

FINALLY, I am free!!

If a nerd girl (otaku preferred) wants to become my girlfriend and lives in Mexico City, feel free to visit my dating profile.

Anyway. My current job is still going to be very demanding for the next two weeks. Maybe then I'll be able to resume work on Saya.

Until then, so long!

First day at job

2009-06-01T20:19:00.000-07:00

At least I got a new job, but I'm beginning to understand that phrase about earning the bread with one's sweat.

The job was supposed to be from 9 to 6, but due to schedule reasons, I'll have to be from 8 to 7, AND 4 additional hours on weekends. At least for these two weeks.

I don't think I'll be able to work on Saya for a while.

I'm beginning to wonder if the project is doomed to failure due to lack of time. Sigh.

I GOT A JOB!!!

2009-05-29T16:35:00.000-07:00

Expect a couple of weeks so I can stabilize, and I'll be working on Saya again. Now... what was I doing before I suspended activities? :(

Anyway. Let's hope we haven't lost much time, and the Pitivi guys are really putting money into it. We cannot lose to them!!

Thanks for your prayers, everyone.

Need to check my vision...

2009-05-28T21:19:00.000-07:00

Just this evening, I noticed that reading seemed to be more difficult for me. I noticed that straight lines look wavy on the center of my vision when I look through the right eye.

I need to go to a doctor ASAP. Let's hope I don't wake up blind by tomorrow.

Jesus.

Update (one hour later): I got to bed and one hour later I realized my eye had been hurting a bit this day. I noticed because it stopped hurting. I can see normally again! :D

Thank God!

I guess I need to check myself for hypertension then.

First commit in a while!

2009-05-28T16:33:00.000-07:00

Sashiburi guys. Long time, no see.

I can't really say that Saya development has restarted. I'm still unemployed and I still feel depressed every once in a while (btw, looking for a girlfriend in Mexico city. Anyone?).

In any case, I hope development will restart soon. There's a 50% chance that I get a new job this monday. Wish me luck!

Alergic to certain brands of orange juice...

2009-04-23T12:43:00.000-07:00

For the past 2 or three weeks I've tried to concentrate on developing, but a mild-yet-annoying-as-hell headache always interrupts me just when I try to code, which is around 10 or 11AM.

I just can't concentrate like that. I've tried taking antiacids (it happens to me, sometimes I get headaches when I get gastritis), painkillers, and I even began to fear it might be a tumor.

Today I ran out of the orange juice that mom had purchased. And I didn't get a headache after breakfast today. WTF!?

I feel like an idiot. Fearing cancer when in fact it was just a simple allergy. Stupid orange juice. Let's hope that tomorrow I can recover from these code-less weeks.

Restarting engine... vroom vroom... it works! :)

2009-04-08T20:24:00.000-07:00

Finally! My first day of coding since a full month. Getting my brain to start after a full month of not seeing the code was like losing my way back in a maze. "Huh? Where did this go? What do I do now?"

So I had to start with the simplest of things: The project panel. It only needed a tree and a context menu. Man, did I have to dig in the user manual to find it.

But it worked! :) I'm fresh and ready to start coding again!

... tomorrow :P

On the other hand, I realized why it took me so long to start programming. It seems I have gastritis (or perhaps a stomach ulcer). If I stayed too much without eating, I began feeling hungry, dizzy and with headaches. So now I'm taking medications (omeprazole) to restore my stomach to pristine conditions. Since the first day of medications, I felt better and with more energy. Who would've thought?

On the bad news, I'm STILL unemployed :( Let's hope I find a good job after Easter! :)

The Exhaustion of Saya Developer: Book 2

2009-03-26T08:50:00.000-07:00

It was two weeks of being sick. I was horribly bored and exhausted at the same time. Some friends of my family invited us to take a vacation, invitation which I accepted joyfully. We went to [place undisclosed for security reasons] and I had a good time. Finally, I returned home yesterday (with a horrible headache, btw).

Now I'm finally resting and preparing myself to continue working on Saya (after a full month of interruptions) and to search for a new job next monday.

Boy, what a month.

Quit my job, got the flu...

2009-03-09T20:01:00.000-07:00

Hi guys. I'd like to inform you that due to health reasons I'll be unable to work on Saya for the next few days (a horrible flu). Also I had to quit my job for health concerns (and other reasons I won't be detailing here).

Still, thanks for your support. Sincerely,
Rick.

Converted Project Pane, first bugs appeared...

2009-03-04T21:20:00.000-08:00

The good news: I managed to convert around 90% of the Project Pane (the tree window and popup menus still need conversion), and moved the code away from the main window.

The bad news: The window state saving and loading routines seem buggy... the project pane is not shown when it should, so I had to comment the call that hides it when the main window is invisible.

I do think I spotted the bug - Qt saves the window layout data in binary form, so I had to convert it to base64. However, I haven't tested if the state loading routines work after the change.

(Update (March 9, 2009) : The window state saving/loading routines are now fixed!)

I also spotted some functions that aren't called by the main menu. I need to fix them, too. But now the code seems much cleaner (I removed a lot of wxWidgets UI code that now is generated automatically by QtDesigner.

After seeing how much the code is simplified, I can finally say that I don't regret switching to Qt.

Qt's aboutToShow() signal: Did we find a bug?

2009-02-22T09:58:00.001-08:00

While converting the wxWidgets code to Qt, I realized something. A QMenu's "aboutToShow()" signal is triggered around 30 TIMES whenever you open that menu. So my menu refreshing routines will be called that many times.

The question is: How to work around it?

Update (Feb 23, 2009, 19:35): Alexandru wrote a sample application, and surprisingly for me, the application does NOT trigger the aboutToShow() signal a lot of times per menu, but rather, only once. Which means only one thing:

The bug's mine. Now I need to check out what went wrong.

Update (Feb 23, 2009, 19:43): I see now what happened. The function I used to automate the connection creation was recursive, but I added the aboutToShow() connections on that same function, which, obviously, got called a lot of times.

I moved the aboutToShow connections elsewhere, and problem solved :)

Alexandru gets a trust point for helping me fix this bug. Yay!

Mom's feeling better, and progress has been made!

2009-02-19T19:58:00.000-08:00

Good news people!

The first, is that my mom is feeling better :). She's under treatment and the fever is gone. In a month we'll see how her kidney is doing.

The second good news, is that the event handling code has been finished and the Welcome dialog is functional (but still ugly).

The one-month goal for the Qt4 conversion deadline now seems possible. Stay tuned.

Alexandru's video demo.

2009-02-15T17:28:00.000-08:00

Alexandru sent me a demo of filling an area of the screen with a determinate pattern of pixels. I modified his demo a bit so it would display random pixels, and so I could find out which bits corresponded to which color.

After a while, here's what I got:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include <X11/Xos.h>

/*demo took from a saya example*/
void fill_image(char *data, int w, int h, int bpp) {
 int x, y;

 char *adr;
 for (y=0; y<h; y++) {
     for (x=0; x<w; x++) {
         adr = data + (y * w + x) * bpp;

         unsigned long pixel;
//            if(!(x % 10)) {
//                pixel = 0xFFFF0000;
//            } else if (x & 1) {
//                pixel = 0xFF00FF00;
//            } else {
//                pixel = 0XFFFFFFFF;
//            }
         unsigned int r = rand() & 255;
         unsigned int g = rand() & 255;
         unsigned int b = rand() & 255;
         pixel = (b << 24) | (g << 16) | r << 8;

         *adr = pixel>>24;
         *(adr + 1) = pixel>>16;
         *(adr + 2) = pixel>>8;
         *(adr + 3) = pixel;
     }
 }
}

void clear_image(char *data, int w, int h, int bpp) {
 memset(data, 0xFF, w * h * bpp);
}


int main() {
 Display *m_display;
 Window m_window;
 GC m_gc;
 Visual *m_visual;
 int m_screen;
 unsigned int m_width;
 unsigned int m_height;
 unsigned int m_x;
 unsigned int m_y;

 XImage *image;

 XEvent event;

 XSizeHints hints;
 XSetWindowAttributes attributes;

 int format;
 int offset;
 char *data;
 int bitmap_pad;
 int bytes_per_line;

 unsigned int depth;
 int bpp;


 if ((m_display = XOpenDisplay((char *)0)) == NULL) {
     printf("cant open x connection\n");
     return -1;
 }
 m_screen = XDefaultScreen(m_display);

 m_visual = DefaultVisual(m_display, m_screen);

 depth = XDefaultDepth(m_display, m_screen);

 /*list supported depth for demo purposes*/
 int count_return;
 int *depths = XListDepths(m_display, m_screen, &count_return);
 if (depths) {
     int i;
     printf("supported depths:\n");
     for (i=0; i<count_return; i++) {
         if (depths[i] == depth) {
             printf("%d [default]\n", depths[i]);
         } else {
             printf("%d\n", depths[i]);
         }
     }

     XFree(depths);
 }

 /*list pixmap formats for demo purposes*/
 XPixmapFormatValues defaultPixmapFormat;
 XPixmapFormatValues *pixmapFormats = XListPixmapFormats(m_display, &count_return);
 if (pixmapFormats) {
     int i;
     for (i=0; i<count_return; i++) {
         printf("depth:            %d\n", (pixmapFormats + i)->depth);
         printf("bits_per_pixel:   %d\n", (pixmapFormats + i)->bits_per_pixel);
         printf("scanline_pad:     %d\n\n", (pixmapFormats + i)->scanline_pad);
         if (depth == (pixmapFormats + i)->depth) {
             memcpy(&defaultPixmapFormat, pixmapFormats + i, sizeof(XPixmapFormatValues));
         }
     }

     XFree(pixmapFormats);

     bpp = defaultPixmapFormat.bits_per_pixel / 8;
 }

 m_width = 200;
 m_height = 100;
 m_x = 500;
 m_y = 500;

 attributes.event_mask = ExposureMask | KeyPressMask;
 attributes.background_pixel = BlackPixel(m_display, m_screen);

 /*depth 32 doesnt work !!*/
 m_window = XCreateWindow(m_display, XDefaultRootWindow(m_display), m_x, m_y,
         m_width, m_height, 0, depth, InputOutput, m_visual, CWEventMask | CWBackPixel, &attributes);

 if (!m_window) {
     printf("error creating window\n");
     XCloseDisplay(m_display);
     return -1;
 }

 /*set size hints for window*/
 hints.min_width = hints.max_width = m_width;
 hints.min_height = hints.max_height = m_height;
 hints.flags = PSize | PMinSize | PMaxSize;
 XSetWMNormalHints(m_display, m_window, &hints);

 /*set windows title*/
 XStoreName(m_display, m_window, "X11 Saya");

 /*create graphic context*/
 m_gc = XCreateGC(m_display, m_window, 0, NULL);

 /*display the window*/
 XMapWindow(m_display, m_window);

 offset = 0;

 /*alloc data buffer for storing image*/
 if ((data = (char *) malloc(m_width * m_height * bpp)) == NULL) {
     printf("error malloc");
     //free x structures
     return -1;
 }
 memset(data, 0, m_width * m_height * bpp);


 bitmap_pad = 32;
 bytes_per_line = m_width * bpp;

 image = XCreateImage(m_display, m_visual, depth, ZPixmap, offset, data, m_width, m_height,
                 bitmap_pad, bytes_per_line);

 if (image == NULL) {
     printf("error creating image\n");
     free(data);
     return -1;
 }

 int step = 1;
 while (1) {
     XNextEvent(m_display, &event);
     if (event.type == Expose) {
//            printf("expose\n");
         XClearWindow(m_display, m_window);
//            if (step % 2 == 0) {
//                clear_image(data, m_width, m_height, bpp);
//            } else {
             fill_image(data, m_width, m_height, bpp);
//            }
         XPutImage(m_display, m_window, m_gc, image, 0, 0, 0, 0, m_width, m_height);
     } else if (event.type == KeyPress) {
         /*size up the image*/

         m_width += step*5;
         m_height += step*5;

         XDestroyImage(image);

         data = (char *) malloc(m_width * m_height * bpp);
         image = XCreateImage(m_display, m_visual, depth, ZPixmap, offset, data, m_width, m_height,
                 bitmap_pad, 0);
         if (image == NULL) {
             printf("error creating image\n");
             free(data);
             return -1;
         }

         XResizeWindow(m_display, m_window, m_width, m_height);

         step++;
         if (step == 10)
             break;
     }
 }


 XDestroyImage(image);

 XFreeGC(m_display, m_gc);

 if (m_window) {
     XDestroyWindow(m_display, m_window);
 }
 if (m_display) {
     XCloseDisplay(m_display);
 }

 return 0;
}

And here's the result:

With some more effort, we'll be able to reproduce a computer-generated video in realtime. At least in X11, the windows driver will use other code. Thanks a lot, Alexandru! Keep up the good work!

Mother's ill...

2009-02-14T13:19:00.000-08:00

My mother got a kidney stone, and until she gets the stone removed I'll have to help her do the dialy chores, so I guess I won't have free time to work on Saya for the next 2 or 3 weeks.

Sorry guys. I'll keep in touch.

My books finally arrived!

2009-02-04T16:30:00.000-08:00

Herb Stutter: Exceptional C++

and

Hughes & Hughes: Professional Multicore Programming.

Yay!

Programmer's block

2009-02-02T19:09:00.000-08:00

I hate it when this happens. The conversion to Qt might seem easy at a glance, but then you realize there's so much to do, and don't even know where to start.

The worst part is that I had the whole day to program, and I couldn't do anything (well, I updated the website). What a waste.

Anyway, finally I realized I should leave the main frame for the end, when the rest of the functionality is ported. So I'll start to work on the welcome dialog. Let's hope I can do that this week.

Sigh.

Status update...

2009-01-28T20:16:00.000-08:00

The only work I've been able to do on Saya this week is copying the Main Menu from wx to Qt, and that was on the weekend.

The reason: I had to sleep at 3 o'clock on Monday and this has exhausted me. Probably I won't be able to work on Saya until Saturday after I've had a VERY GOOD sleep.

On the other hand, this Friday we'll have the developers meeting. Two people will be joining the team, and two people will be leaving. Let's hope that I can finish the Qt conversion for the end-of-March meeting so we can move on.

Wish me luck!

Report on the non-advance of the project.

2009-01-19T21:07:00.000-08:00

My job's killing me. I haven't been able to work on Saya the last week, and I this week there will be only a 50/50 chance I can get to work on it.

On the other hand, it seems I've managed to gather not one, but TWO volunteers. One will work on the mascot (yay! ^_^) and also has some Qt experience. The other one... I forgot, sorry.

Wish me luck and some free time!

Good night.

Report on the Qt conversion

2009-01-11T21:19:00.000-08:00

Hi everyone. Just a quick report on what I've been doing today.

I've been having a hard time converting the application to Qt. Basically, I've had to take a decision: To adapt the C++ code directly to use the eventid#'s and get rid of Qt designer advantages, or workaround the autogenerated code by writing some wrapper functions and write LOTS, LOTS AND LOTS OF CODE.

The advantages to the Qt designer are obvious. Easy code generation, forward compatibility, etc.
But I've grown tired of how wxWidgets loads the UI using xml libraries. Is that REALLY necessary?

I realized I wouldn't need to choose between the two. Why? Because Qt designer lets you see the generated code! :D

I only have to copy/paste the code, just like I've been doing with wxFormBuilder. Also, I realized I didn't need to write a lot of code. Remember this?


int idFileOpen = XRCID("idFileOpen");

I can easily rewrite the Id registering functions into this:


unsigned int idFileOpen = syActionEvent::RegisterId("idFileOpen","OnFileOpen()");

Wait, what's that second string for?
This is the beauty of thinking out of the box. We don't have to follow wxWidgets' model anymore! We're FREE To do whatever we want! So besides registering a numeric id for the File-Open event, I can also register the Qt slot name that gets triggered by the corresponding action!

Later I only have to write a small function that recursively iterates over all QActions in the main menu, gets the corresponding Id, and connects to the slot at the same time.

But all this thinking really made me get tired of the Qt conversion issue. Yes, I have to admit it, it's boring (coding without visual feedback isn't exactly a rollercoaster ride). So it's better if I rest for a bit and then later next week I'll go on with the conversion.

Oyasumi nasai (good night).

Actions, events, slots, OH MY!

2009-01-10T19:04:00.001-08:00

I've come to realize that Menu Event Handling in Qt is versatile, but it suffers from a fatal flaw:
It relies on slots. In other words, if I have to run a specific event (like Opening a File), I need to call the object's specific slot either directly, or via a signal. For that I need to actually include the class' header file. And that's a no-no.

So what am I gonna do? At this time I'm glad I implemented Saya's event system. With it, I can replicate the old "call an event with a specific ID" behavior. That's much better IMHO than having to include a huge header file.

But before that, we need to create a new class: syActionEvent. Which basically is a reimplementation of wxWidgets' menu event.

Update (Jan 10, 2008, 21:50):

I just realized that to send a menu event you just have to allocate an action. So you'll end up
with a series of action pointers. That would be the elegant solution - but isn't it more elegant to simply have a series of integer values, with no pointers allocated to them? So that's what we're doing in here. Yes, I know, we'll have to create the actions ANYWAY because that's how Qt works. But as I already said, I don't want to be tied to a specific event model. And using numeric id's for events is simpler, IMHO.

GAAAAAAAAAAHHHHHHH!!!!!!

2009-01-08T18:47:00.000-08:00

There's so much code to convert to Qt!!!! (sorry, had to get it out of my system)

I need to take a break.

(On the other hand, I'm so glad I decided to convert before advancing any further! :D )

The MOC: Qt's lethal trap!

2009-01-08T16:29:00.000-08:00

Having learned how cool the QT+Python combo is, it had never occurred to me that for C++ you need to go through a very different path to implement signals and slots with Qt.

What are signals and slots? They're the coolest possible way to implement events. A slot is defined by a specific type of function (which receives a specific type of parameters). A signal is just a function. When you connect a signal and a slot (or various slots), all slots get triggered by the same signal.

But to implement this in C++, the Qt guys chose to use a meta-object-compiler (MOC), which means you have to PREPROCESS your cpp file in order to compile it. UGH!

I've been trying to find an alternative way, but all my attempts have failed. The code generated by the moc is both cryptic and hideous, worthy of an obfuscated C contest.

But not everything is lost: After we change a c++ file, all we have to do is run the MOC on the file and redirect it to a moc header (which we will manually include by the cpp file). The trick is generating the moc file automatically.

Enter Qmake.

*disc scratch sound* NOOOOOOOOOOOOOO! I don't want to run Qmake, dammit!

OK then, enter CMake.

Ah, that's much better :)

Guess what? CMake has built-in support for Qt's MOC! All you have to do is add some parameters to your CMake file, and voila... I think.

Sigh. I didn't want to do this already, it's too soon! I don't want to be a father! (sob). Sorry, got carried away :P

For now, I'll build the moc files by hand (which will suffice for now), and then, I'll add the necessary stuff when I make the move to CMake.

This is Rick, and I approve this message.

It's official: We're moving to Qt4!

2009-01-05T10:28:00.000-08:00

I finally made up my mind. After an e-mail conversation with one of the VLC developers, I was told that they submitted quite a few bug reports to wxWidgets, and they were all dismissed. I was also told that wxWidgets was very difficult to work with, and recommended to work with GTK, QT, or anything _else_ (wow, is wxWidgets that bad?).

And my experience confirms it.

Now, I tried the QT4 dialog designer, and once you get the hang of it (you need to use a right-click menu to put all the controls in a layout, there's no standard button for that), it's a bliss. But is it compatible with GPLv3? Version 4.3.4 and up are. Hurray! :)

Sigh, so here goes YET ANOTHER month of changing existing code for arbitrary reasons. I'm lucky I had already adapted a lot of code from wxWidgets ;-).

I'll close this announcement with a famous quote:

"Chance favors the prepared mind".
Louis Pasteur

VLC knows best.

2009-01-03T23:43:00.000-08:00

I hadn't realized it, but turns out that VLC, my favorite video player (due to its stability, etc), uses wxWidgets!

And I just found a Doxygen page documenting every single bit of it. Man, this thing is a masterpiece of art. I think I'm going to start stealing^H^H^H^H^H^H^H^H borrrowing code from VLC :).

So far, I learned that VLC uses the following approaches to draw video:

XV (hardware-accelerated Xvideo extension to the X11 server)
X11 (100% software)
GLX
SDL

All of these, in the form of plugins. Just what I was looking for.

Unfortunately, that means one thing: My current framework design doesn't seem to be extensible enough. I wrote a VideoOutputDevice class, which was supposed to take care of this. But, how to integrate it with a hardwired set of video control widgets?

VideoOutputDevice has a function to Set the size. And now I'm starting to see something else that I missed. Before now, I didn't actually NEED the VideoOutputDevice to remember the width and height - that was something that wxVideoPanel had. But now I'll need to specify not only the width and height, but also top and left (relative to the current screen), so that we can use any direct rendering plugins.

I'll also need to add a registry of VideoOutputDevice classes, and generalize wxVideoOutputDevice into a more generic class. Or actually, add a new class: syBitmapSink. The only thing this class will do is to load data from a syBitmap. This way, we will be able to use a "Default" VideoOutputDevice, which on Flushing, will send the data to a syBitmapSink. And wxVideoPanel will be that sink.

Since the object coordinates, width and height will change dynamically, the new VideoOutputDevice subclasses will have everything they need to perform the rendering. So it's all matter of which class gets instantiated on startup.

Neat, huh? :)

...and Pandora's Box was opened.

2009-01-03T19:19:00.000-08:00

Oh my, look at all these bugs! Will the Playback framework will ever be completed?

And just when I thought everything was going fine, I realized that playback had a lot of bugs and design flaws.

* Playback didn't sleep at all, so it was caught in a loop waiting for the time when the next frame had to be painted. (fixed in my PC).

* The current frame is reset exactly at 4.0 seconds from playback. This is a very curious behavior, but I haven't found out (yet) why it happens.

* After pressing pause, pressing play resets the current frame to 0 again. And I don't know either why this happens. Sigh.

* Rendering the current frame into the screen is SLOW AS HELL. Why? Because we're using wxWidgets events for painting, and that's just wrong. Rendering should be done IN THE RENDERING THREAD. But there's a problem... how do I paint directly to the client window from a thread? I need to research more about this.

In any case, I'm glad I wrote one unit test for the time/frame conversion. I also wrote some other unit tests in the form of painting algorithms. The two bugs mentioned above were caught with a straight line painting video: A vertical line, whose x coordinates are equal to the current frame. I don't have the means to print a text in a bitmap, so I have to use what is available.

Video playback engine WORKS!

2009-01-02T20:13:00.001-08:00

Finally I realized why the CPU hogging. I hadn't implemented the Video Output code (all video output was still done in the testing code, in the main thread :P ). But now we can play, pause, fast forward... reverse playback hasn't been tested yet. I need to modify the Demo Video code to see if it actually works (audio, on the other hand, hasn't been taken care of yet).

On the other hand, a friend JUST recommended me to use the Xine engine. Sigh. Why didn't I find out earlier!! Still, xine only works partially on Windows... on CVS. Oh well, what can we do about it?

This leds me to think about it. Why is it that when someone tries to make something that works, nobody helps him but everyone is eager to criticize? People from IRC laughed at me. Meanwhile, support and/or suggestions didn't come. Well, some people did help me, that's why they're on the team. But still, no experienced programmer. What am I supposed to do all alone? Oh, I forgot about the mailing list guys, they also provided valuable help. Unfortunately, everyone's working on his own project.

If a good C++ programmer is reading this, PLEASE HELP! I can't do it all by myself! It's been more than 7 months already, and I'm still on my own. Maybe someone will help when the project advances further.

See ya.

It's alive, Igor!!! It's... having seizures?

2009-01-01T14:10:00.000-08:00

After a lot of debugging and refactoring code, I finally got the Playback manager to work... and crash / hang.

First of all, I had overlooked a lot of things while coding the playback framework. I hadn't been given a single opportunity to ACTUALLY test it. But now that it kinda works... the bugs/flaws started to appear, one after another.

For starters, CPU utilization goes to 50% when PAUSED, and 30% when RUNNING. O.o
Second, on exit, for some reason that I haven't determined yet, sometimes I get segfaults, and sometimes hangs.

But at least I'm getting closer: The play/pause button interrupts and continues playback :)

I'll commit the code to the SVN tree when these bugs get fixed.

Update (Jan 1st, 2009):

I *think* I know what's happening. It's during ~AVController(). The VideoInputDevice object generates a segfault when accessing one of its mutexes. But if we get a segfault, it means that this location is no longer valid. In other words, we're dealing with a dangling pointer. Which means that somehow, the VideoInputDevice already got deleted somewhere else. But when, and how?

Update (Jan 1st, 2009, 19:55):

Ah, I see what happened.

AVController's destructor calls AVDevice::ShutDown(). But when InputMonitor (which is a subclass of AVDevice) deletes its Video Input Device on destruction, it fails to reset the pointer. So when ~AVController() calls ShutDown(), we're operating on an already-released object. In other words, in the destructor chain of InputMonitor, we deleted an object prematurely. The problem was easily fixed by simply commenting the deletion line.

Also, there's no resource problem with ~InputMonitor, because it always uses the same InputDevice. Besides, InputMonitor only gets created and deleted once. So how is InputMonitor's FileVID object deleted?

With a new class I created, AVDeviceRegistry. On deletion (that means the program's shutdown) it deletes all created AVDevices. And when an AVDevice is deleted, it unregisters itself from the list. Ta-da!

Now that the app doesn't crash on exit anymore, we're ready to commit to SVN, and later fix the CPU-thrashing Issue. Yay!

First bugs found! :)

2008-12-28T20:31:00.001-08:00

The good news: I found new bugs in the playback module.
The bad news: I found new bugs in the playback module! :D

When the AVController is paused, I haven't yet implemented a way to signal the main thread that it's paused. See, we have to check not one thread, but four. So that means we can't use a single flag, but four.

The problem is, we need to detect different conditions:

If the thread is invalid,
if the thread is valid but paused,
if the thread is running,
if the thread has stopped.

And this for each thread. But we need to check if the threads haven't aborted abruptly.

At least we're closer to getting this to work.

Update (28/Dec/2008, 11:41PM):

The play/pause bug has been fixed now :). No more deadlocks! Now we're going to test the Demo (the blue colored figurines in the screenshots) using AVController. But that'll be for another day, I need to go to sleep, it's very late already.

G'night.

Video Playback controls advancing...

2008-12-27T20:14:00.000-08:00

Good news (as usual ;-), I've managed to tie the AVController class (actually, the AVPlayer class, which is a subclass of AVController) with the playback buttons.

Whenever I press "play/stop", the AVPlayer instance receives a play or a stop event (a Saya event, not a wxWidgets event - this is what makes it important, because it makes our core classes still toolkit independent). Same goes when I press "fast forward", "fast rewind" buttons, etc.

I'd post a screenshot, but a screenshot of a messagebox is pretty boring.

In any case, now I have the tools to start testing the playback framework I've been working so hard during these 4 months.

I'm so excited! I feel just like Dr. Frankenstein waiting for the thunder to bring my creature to life, mwahahahahah!

The C++ Source: A wonderful C++ website

2008-12-26T09:07:00.000-08:00

The C++ Source is an online journal about C++ programming, it covers many advanced topics including advanced (and often below-the-radar) uses of C++ templates.

I also read two very interesting articles:

Top C++ Aha! moments"
Top C++ non-book publications

First donation received, and wxSlider skipping problems.

2008-12-25T20:19:00.000-08:00

First of all, thanks to Zarxrax from Doom9 for his generous donation to the project.

That said, I'd like to complain about wxSlider. The wxWidgets code for the slider widget has this annoying behavior: If you click on anywhere in the slider, the slider reacts as if a pageup/pagedown had been pressed. I absolutely hate that. Sometimes I want to repeat or advance a DVD scene in VLC player, to have the player skip around 20 minutes or so because I didn't grab the slider control correctly. ARGH!

This can be solved by making the page size to 1/50 of the total slider length. It's still not perfect, but that's the only workaround. But I'm definitely considering writing my own slider control. Now, where was that native widgets implementation I saw the other day on the web?

A lot of advancements... behind the scenes.

2008-12-23T20:22:00.000-08:00

Merry Christmas everyone! I have good news, and not-so-good news.

The good news is that a lot of work has been done on Saya. Especially the last 2 days, because I got sick and had to stay at home, so that gave me a lot of free time :P

Here are some advancements that have been made:

Since I was asked to code Saya in QT4 (as opposed to wxWidgets), I've been working really hard on getting rid of wxWidgets dependencies. So that means I had to make a lot of wrappers, substitute classes, etc. These include but are not limited to:
1. A completely new, template-based, event handling system. Saya classes can now emit and receive their own events! Unfortunately there was no way to get around glib's (gtk) main_loop - but since even Qt made a wrapper around it, it's better to use what works. So I had to make a new wxWidgets event type to signal wxWidgets that a new Saya event has been queued. So far the only time I use an event is to signal the Main Frame that the currently-active project has changed.
2. A completely new syApp class: Saya is becoming more like a cross-platform toolkit (with more and more files in the core/ path) and less like an application, but that doesn't worry me. The point is that I managed to invoke the wxWidgets UI with a function from the plain old main() function. This also means that we could turn Saya into a non-graphical tool.
3. With the new syApp class (and its subclass wxSayaApp using wxWidgets), I no longer need the sayaEventHandler class, and I no longer need the main window to have its own functions for opening dialog boxes. All dialogs from now on are invoked by syApp. I even added a syFileSelector function. This also helped me remove some wxWidgets-specific includes.
4. The new syString class (a class encapsulating a const char*) does everything we need from wxString, including efficient concatenation, conversion from various numeric types, printf-like formatting, etc. And because I added some conditional includes, you can convert from/to wxString without having to call a function (the only exception is when a wxWidgets function needs a const wxChar*, you need to do the casting specifically: wxString(mystring).
5. Along with the new syString class, serialization and de-serialization will become piece of cake when I get to implement it.
6. The source code tree has been reorganized. Now we have the following directories:
  
  ui/ (all the code using wxWidgets, and our main application)
  
  saya/ (The directory for our video editing framework)
  
  saya/core (The directory for our generic cross-platform application framework)
  
  saya/timeline (The directory for our timeline-specific classes).

Some bugs in the ioCommon namespace (I really have to put my namespaces in order) have been fixed, like renaming / deleting a file.

Most classes have been moved to the private implementation parts, and this has helped me get rid of TONS of unnecessary includes. With these changes, we can recompile Saya (without -O2) from scratch in only 22 seconds.

Memory handling has been given special care: For temporary objects, now we use std::auto_ptr whenever possible.

I've created the following classes: AVPlayer, InputMonitor, PreviewMonitor (well it's now coded yet, but it'll be a minor adaptation of InputMonitor). AVPlayer also inherits syEvtHandler, meaning it can catch events you send. I'm *very* close to actually being able to reproduce video thanks to this.

So that's the good news. The not-so-good news is that I haven't been able to get video playback to actually work... yet. It's a very steep curve, but I'm sure all my work hasn't been in vain. I promise that next year I'll actually have a workable media player for Saya.

Merry Christmas, and happy new year!

Building Saya with CMake... Coming soon!

2008-12-19T16:54:00.001-08:00

Hello everyone. For some time i've been considering building Saya without requiring to install Code::Blocks and wxWidgets (which is a hassle for beta-testers - they just want to run a script and have it compile Saya so they can test it right away).

Here's the forum post which made me consider everything:
http://ubuntuforums.org/showthread.php?t=692692

After giving a glimpse over various automation tools, two tools called my attention: SCons, and CMake.

SCons is a tool supposedly cross-platform tool which I need to use at work. It uses python scripts. UGH, python! So, why did it call my attention? Because of its complexity and python requirements. In other words, it's a tool I would NOT like to use :)

The alternative was CMake. We know CMake has support for Code::Blocks projects and workspaces (that's a plus!). But I was delighted when I realized that CMake is the tool used to build KDE 4.
http://lwn.net/Articles/188693/
Wow.

The best part of using CMake is that the only thing you need is:
a) Your compiler
b) CMake

Autotools and SCons, on the other hand, require you to install more scripting languages (i.e. perl, python) to make your file. This is REALLY what I like about CMake. It's lean.

Next year I'll start to work on being able to compile Saya with CMake.

Spammers starting to annoy me

2008-12-08T06:00:00.001-08:00

There's an idiot who wants to promote his non-free video editing software on my blogs. This means I'll have to moderate all comments from now on. Which is a good thing, because now I'll find out who posts comments.

Oh, just for your amusement, here's a copy of the e-mail I got from blogger:

淑丽 has left a new comment on your post "Saya developers meeting #3 (2008-11-28): Summary o...":

(VideoEditorSoft dot com - link de-httpified to prevent more spamming) provides free easy and popular Video Editor,
Video Joiner,
Video Splitter,
Video Cutter,
Video Clipper,
Video Merger,
DVD Video Editor,
DVD Video Author.

If you are looking for video Editor for Apple Mac OS X program, please refer to Mac Video Editor,
Mac DVD Video Editor.

Posted by 淑丽 to Saya Video Editor official Blog at December 7, 2008 9:49 PM

Just so you know, his profile id is available at http://www.blogger.com/profile/12311597430950642116 If he tries to post again, I'll notify blogger so they can kick him out. :)

By the way, I really *DON'T* recommend downloading from his site, who knows if that thing's got a virus or something.

Got rid of some of the STL classes, reorganized stuff...

2008-12-07T07:04:00.000-08:00

I was talking with the author of the uSTL about how to avoid STL code bloat, and I ended up asking him a question about strings. He told me that to concatenate strings I should use the ostringstream class for concatenations.

So I began to replace the references to std::string in the timeline classes, and designed a new form to serialize them.

I made a C++ wrapper for ostringstream so that I could later switch classes in case I needed to. Guess what, I did switch later. Because I also needed to design a std::string lightweight replacement (I've called it syString), I ended up adding methods to concatenate strings in an efficient way. I use the "size doubling" technique, up to a certain point, then the string only increases by amounts of 64K. I haven't tested this strategy well, but I may change the strategy in the future by adding a static parameter.

I also reorganized the header files and cleaned up a lot of bloat. Some classes included the STL (I still need std::map and std::vector) for fixed types, so I moved the std inclusion to the CPP.

I also fixed the precompiled headers inclusion, and removed a lot of unneeded wxWidgets includes from the GUI files.

As a result of this optimization, I've cut compilation time by 33%, yay! :)

Unfortunately, I stopped working on the playback engine, but I'll start. Playback functionality needs to be finished and tested ASAP.

Playback widgets status

2008-11-22T19:42:00.001-08:00

The playback widgets have been uploaded to SVN, but they haven't been integrated into the project, as they need more work. But soon we'll be able to load and play a "dummy" video file. When playback is done, we'll move on to deal with the codec issues.

Slow but sure advances in the playback...

2008-11-16T18:46:00.001-08:00

I've moved some of the private properties of classes VidProject and ProjectManager to the .cpp. This will allow me to skip recompiling some modules whenever add a private member to the classes.

Also, I've managed to create my first instance of AVController (member of the hidden ProjectManagerData class). I hope to have the demo running on threads in the next few weeks.

Also, Rigo is working on the playback controls using wxFormBuilder. Here's a sneak peek:

When it's done, I'll add this control to the wxVideoPanel, and finally our editor will start to look like... a Video Editor :)

Playback widgets advancing...

2008-11-14T13:54:00.001-08:00

Rigo, Jeff and me have been discussing the design and implementation of the widgets for playback control. Rigo's really pushing himself to work soon on it.

I'll let you know when we have something working.

Finished the first "official" week in my new job!

2008-11-14T13:45:00.000-08:00

Finally I've been given work to do other than reading manuals and documentation.

I'm currently working for a web filtering company. They develop an all-in-one solution for filtering SPAM, viruses, porn, phishing sites etc.

The good news:

* The environment in here is very friendly. We're not forced to wear specific clothes, the time to eat is at the worker's discretion. It's very relaxing.

* The methodologies followed are pretty neat: We have a wiki, we use Mantis issue tracker, have a subversion repo, there are coding guidelines, and some of the code have very interesting patterns. It's like my dream job! :D

* Now that I've studied some of the code of the company's products, it's like every hacker's dream come true: TOTAL control over internet traffic, sending RST packets to block P2P traffic, (I won't discuss the morality of sending RST packets, that's up to the customers to apply them or not - but the appliances can be used at home, for companies intranets, etc -, man-in-the-middle eavesdropping for https transactions...

Neo: Whoa.

The bad news:

* The schedule. You start working at 7AM :( This leaves me exhausted for the rest of the day, which unfortunately leaves me too tired to work on Saya. I really hope I can advance during the weekends.

But I love it! And the pay's definitely worth it.

It's DLL time...

2008-11-04T18:47:00.000-08:00

It's time to split the project into its components.

Saya is originally meant to be a wxWidgets application running on top of two shared libraries: "libsaya", which handles all the editing, and "libsayacore" which does the very low-level multimedia stuff. libsaya depends on libsayacore, of course.

For this I've had to do some wizardry and rename the vidproject/ directory into saya/, and move the iomgr/ directory into saya/core/ .

Now, I really don't know how I'll do this shared libraries stuff, but I still can check the codeblocks source code :)

First rule about the fight club...

2008-11-02T13:00:00.000-08:00

you do not talk about the fight club.
Second rule.. you DO NOT talk about the fight club.

So, I joined the fight club. Actually it's more like a secret mailing list whose owners happen to be working on multimedia projects. Those might or might not include video editing. One of the current threads in the mailing list include comments and experiences about some open source multimedia toolkits, like MLT and gstreamer.

Unfortunately I cannot give any more details of who the members are and what projects they're working on. But it's getting very interesting. Hopefully I will gain enough knowledge to perfect my own toolkit.

I'll keep you posted.

Back in the saddle again... kinda.

2008-10-22T21:54:00.000-07:00

After nearly 3 weeks of not writing any code, I finished making some changes to VideoOutputDevice class. The class methods LoadVideoData and FlushVideoData are lock-free with respect to each other. This means that while I'm writing data into a bitmap, I can write the previous bitmap into the screen.

In any case, tomorrow's my last day at my current job, and I really don't know how late i'll be returning from home. And this Friday I'll go visit my new job. I need to return early home because then we'll have the October meeting for the Saya devs.

Let's hope my new job gives me enough time to work on the project. Wish me luck!

Finished installing and customizing Mepis. Hurray!

2008-10-12T17:58:00.000-07:00

I finished making the necessary modifications and software installations to my distro. You know what? I actually had to read the Saya-VE developers' guide for GNU/Linux :P. In any case, I already managed to compile and run Saya.

Hurray! Now I can continue developing... on GNU/Linux. I won't be able to debug the Windows version until I install VirtualBox, tho.

From PCLinuxOS to Mepis: Painful, but worth it!

2008-10-10T19:17:00.000-07:00

If you've installed PCLinuxOS with an advanced partitioning, prepare for a painful surprise. SimplyMEPIS (up to 8.0 beta 2) doesn't let you install /usr, /var and /tmp into the partitions of your preference.

Which means that once you've logged in, you need to enter the console (through ctrl-f1), mount the other partitions, delete their contents, cp -a /usr /your-usr-partition-mount-point, rename the other partition, edit fstab, etc. etc. etc.

It's not something that you can do while in the LiveCD (I've tried to an extent and I failed miserably).

Also, if you've used a non-standard file system such as XFS, just forget about it. You need to mkfs.ext3 the other partition (in this case, /tmp) and then proceed. Speaking about /tmp, an additional step is required: You need to delete /tmp, which is a symlink to /var/tmp.

--

But after I managed to do all that manual installation work so that I retain the structure of my partitions (which I carefully tuned), I'm actually enjoying it.

For starters, you get nVidia support right out of the box. I booted the LiveCD in 1280x1024 with no problems whatsoever.

The KDE provided with Mepis 8 is awesome. It's not KDE4, but 3.5.9, and that gives you stability. But this KDE is better configured than the one with PCLinuxOS 2007. I can pump the volume up and down with my multimedia keys. In PCLOS, I had to set up the mixer manually (not without the help of some friends on slashdot and irc) and add some lines in some obscure alsa config file.

The kernel: PCLOS2007 ships with 2.6.19, and the latest upgrade is 2.6.22. Mepis 8 ships with 2.6.26, which also means support for tons of more wireless and external devices.

Package management: The Synaptic package manager is also provided as default (yay!), but Mepis provides an excellent addition: The actual applet tells you how many upgrades are available. And finally, there's no "pay-for-upgrade" policy. The latest packages are already available for no additional price (like Firefox 3.0.3, which I just downloaded an hour ago), and the repositories are based on Debian, one of the most community-supported repos. Try to beat that, Tex!

In short:

If you're stuck in PClinuxOS and want to try a debian-based distro, the upgrade is painful (unless you happen to have installed in only one partition), and you need to delete your packages - for compatibility - anyway. But it's really worth the upgrade, provided you manage to install prettier themes. Personally, the default ones suck - but hey, it's a beta version. And no crashes! :)

If you're undecided between PCLinuxOS and Mepis, go for Mepis. Nothing beats getting connected to the default Debian repos.

Mandriva, distro headaches... and Mepis 8.0 beta 2

2008-10-09T21:35:00.000-07:00

Sigh. I only finished downloading the Mandriva 2008 ISO so I could burn it tonight and install it. I chose Mandriva because its configuration is the closest to PCLinuxOS.

First bad news: I realized that I didn't download the most recent 2008.1, but the outdated 2008.0! ACK! 4 hours wasted.

Second bad news: Mandriva 2009 is out, and yet, it has lots of bugs. I'm not going to upgrade to a distro which freezes the GUI every now and then. What is this, Windows?. Also, I couldn't find the 2008.1 isos because the mandriva guys made them unavailable from the web. I had to use Google to find it. Now it's nearly 34% complete.

Third bad news: 2008.1 also has some bugs, and it's definitely annoying that the guys don't have the time to release a 2008.2 with all the bugs fixed - and no new features. No, instead they chose to go for KDE 4, an unstable branch of the Linux kernel, and lots of bells and whistles. I don't want to cut my hand with a bleeding-edge distro. I want something that JUST WORKS!

Therefore, I decided I'll use MEPIS.

Why Mepis?

1) It uses KDE! :D And the 3.5 branch! :D :D

2) At first it used the Ubuntu repository, but now it switched to the latest Debian - can't be any more stable than that!

3) It's a debian distro! Lots of packages are distributed as .debs.

4) According to this Linux discussion, Mepis is even more stable than Mandriva. And this other discussion gives me the impression that Mepis has surpassed Ubuntu.

In fact, I would be going with Ubuntu (most popular distro these days), if not for their negligence towards KDE.

Ah, here's a Mepis 8 review at deviceguru. Just what I was looking for. Hey, what do you know? The review's login screenshot says "Rick". Must be a sign ;-)

For the impatient ones: MEPIS 8 beta 2 (32-bit) torrent - courtesy of linuxtracker.org

I'm tired of waiting, I'll leave my computer on to finish the download.

Switching to Mandriva 2008.1

2008-10-08T19:25:00.001-07:00

Tonight I'll make a bold step: I'll switch away from PCLinuxOS 2007, and move to Mandriva 2008.1 "one". The PCLinuxOS repositories are simply too small and too slow. Plus, Mandriva has the newest kernel.

This will help me with a lot of things - for example, I can try out the latest version of Kdenlive (for research purposes and maybe for making 1 or 2 short AMVS ;-) ). I'll also be able to use the latest GIMP. I tried compiling it on PCLinuxOS, but I just can't figure out how to tell it to compile right.

Anyway, I'll need to back up the important Saya stuff. *GASP* I need to back up my media, too! :( Ugh! Good thing I have a fresh 8GB Flash drive around.

If things don't go well, this may stall Saya development for a couple of weeks. Wish me luck! :)

I decided I'll use PortAudio

2008-10-08T19:21:00.001-07:00

After a little research (actually a web search and a chat), I decided I'll be going to use PortAudio for the audio output. That should complete the components required for Audio Output.

Speaking of audio, I need to deal with using a different number of channels for the input and the output. With the help of Stefano D'Angelo, of naspro.atheme.org, I managed a way to specify to the audio buffers some parameters for conversion. But I doubt I'll have that ready soon - first I need to complete the playback functionality. Later I'll worry about channel conversion.

Google Tech Talks on Youtube!

2008-10-07T19:29:00.000-07:00

I hadn't known this, but it turns out that Google has been posting their tech talks for more than a year.

Two particular talks got me interested: The first, is a presentation made nearly a year ago about the new features in the upcoming C++0x standard.

http://www.youtube.com/watch?v=ZAG5txfYnW4 (Warning: 1 hour video!)

The next talk concerns us more - it's a fast lock-free implementation of a hash table. Hash tables are used in all kinds of programs, but if many threads try to access a hash table, they need to have exclusive access. With a lock-free hash table, you don't need exclusive access to add or remove an item from the table. In fact, you don't even need exclusive access to read the table!

http://www.youtube.com/watch?v=k5FltpgKcVk (warning: another one-hour video!). Here's the lock-free hash table presentation in PDF format.

The Java source code is available on Sourceforge: https://sourceforge.net/projects/high-scale-lib/

Enjoy.

Fixed first thread bugs... and improving :)

2008-10-02T07:14:00.001-07:00

I'm fond to announce that the threads module NOW WORKS! :D

The first test made by Rigo was pretty simple, and I've added a few things here and there. But I've managed to get the module to be more stable than the wxWidgets implementation!

For example, I've added a function that allows you to know if a thread is detached or not. If the thread was deleting itself, under wxWidgets, you could crash the system. The new implementation simply adds the thread to a detached threads list. So we now keep a joinable list and a detached list.

Also, when deleting a detached thread, we remove it from the list (with carefully-placed mutexes) so that you can't really double-delete a thread, even if you try.

I've also fixed a couple of bugs in the pause/resume methods (a stupid bug, I had used a sentry object but the object was never created, I had just invoked the constructor with no object to construct, doh :P ).

So this means I'll now be able to keep working on the playback base module.

In the future I have planned to make the modules separate shared libraries.

Memory barriers and SSE2

2008-09-24T22:22:00.000-07:00

After reading that lock-free code would be unstable on multiprocessor machines (dual cores, etc.), I studied that there was a way to prevent such things from happening: Memory barriers.

A memory barrier makes sure that all the data you've written to memory effectively goes to the memory and doesn't stay in the CPU Cache.

Unfortunately, according to a recently reported GCC bug, GCC's instruction for memory barriers, __sync_synchronize(), is flawed in x86-64 processors (Pentium Core Duo, AMD 64 x2, etc) because it doesn't implement the instruction "mfence".

mfence is an SSE2 instruction (SSE2 is available for Pentium-4 and later processors) that implements an efficient memory barrier. There are other implementations to do a memory barrier on x86 processors, which I won't mention here for reasons of space. So I replaced the __sync_synchronize() primitive with qprof's AO_nop_full(), which invokes a memory barrier, using mfence if available. Also, I added this function to all the atomic primitives, and also to the syAudioBuffer class.

Now I can be 100% sure that the code won't crash. At least for multiprocessor-caused race conditions, anyway. ;-)

"mutable" keyword, and Major rewrite in the core...

2008-09-23T18:14:00.000-07:00

After redesigning the syAudioBuffer and implementing some stuff in the AudioOutputDevice, I realized that my assumption to use only one thread for reading and writing led me to write some very defective code, so I almost have to rewrite the entire thing. Fortunately I have finished doing so with AudioOutputDevice. But VideoOutputDevice, VideoInputDevice and AudioInputDevice are yet to be rewritten. Sigh.

Additionally, I do need to redeclare the majority of functions as const. Fortunately, now I can do so freely because I have discovered the mutable keyword!

mutable allows you to allow some variables in the object to change, even if the modification resides inside a const function, or if the object was passed as "const". This way I can declare the thread synchronization variables as "mutable" and still enjoy the compile-time protection of const.

Update (Sep 23, 2008):

Finally some good results from the rewrite! I discovered a bug in syBitmapCopier that instead of copying the source to the destination, it copied the destination to the source!! :-S Yikes.

It's nice how all these knowledge tidbits contribute to improve a programmers' level as a whole.

Happy 17th birthday, Linux!

2008-09-17T19:45:00.000-07:00

Some hours ago, Linux became 17 years old! I have to mention that after studying the kernel code (because that's what Linux is, a kernel, NOT an Operating System!), I realized that calling the different distributions "Linux" is wrong.

Probably you'll say "aw man, not that Stallman crap again". Nope. It's actually the opposite. I've been having some annoying problems with the Linux DISTRIBUTION (which includes the kernel, the GNU operating system files, KDE and some other stuff) I'm using right now. But saying "aw man, my Linux isn't working" is WRONG. It's not the Kernel's fault! It's the stupid distro's fault.

Because as I have studied the multithread code, the posix mutexes implementation, and read about the Completely Fair scheduler, I realized:

Man, this kernel is one of the most beautiful things created by men. For starters, it implements posix threads, which have a beautiful and simple API compared to... eeew... Windows - trust me, I've been using this thing.

Another example of Linux' beauty is one of the recent patches for the scheduling code, which was merged in 2.6.25. It implements something called ticket spinlocks. To explain, a spinlock is an item that can only be possessed by only one thread at the same time. And all threads keep competing for it, and they never give up until they get it. Not a nanosecond of rest. Imagine a discounts sale on a women's clothing shop. Yes, it gets that ugly :P.

But the latest patch makes each thread take a "ticket" and wait for its turn. When I read that I was like... whoa.... you just blew my mind. I didn't even SUSPECT things like this could be implemented! Even after 17 years, Linux (yes, the Kernel) is getting more and more beautiful.

Now, repeat after me:

Linux. Is. Beautiful.

So now on my to-do list is to replace all the "Linux" references in Saya's website for "GNU/Linux", to give the Kernel (represented by that cute little penguin we call Tux :) ) the place it deserves.

HAPPY BIRTHDAY, LINUX!

As a gift, here's a cute paper tux to decorate your desk. By the way, you can edit the image to replace that logo with your favorite distro's logo. Enjoy the party :)

New AVController design: Four threads, audio frames.

2008-09-15T21:50:00.001-07:00

After not visiting the Audio Video playback/sync module for a while (due to my work with the threads and the API cleanup in the timeline model),I finally decided to print the source code. Believe it or not, it allows you to concentrate better and see the code as a whole. So it was like 20 to 30 pages, stapled per file for a better organization.

Anyway - I studied the code for avcontroller.cpp, and I saw a fatal flaw in the premilinary design: There was only ONE worker thread, and I need four!

Why?

The code does more or less this: It tells the VideoInputDevice to send data to the VideoOutputDevice, which tells VideoOutputDevice to load the data. The problem is that VideoOutputDevice also Renders the data after loading it, instead of invoking a separate thread or something.

So there's a sequence to load the video:

1) VideoInputDevice fetchs the video from a file or whatever. This implies a HEAVY OVERHEAD as it can imply either decoding, or compositing.

2) When the data is available, VideoInputDevice sends the data to the VideoOutputDevice.

3) After receiving the data, VideoOutputDevice sends the data to the display or encoder.

Which means, that while the decoder processes the input, the encoder is blocked. While this can be fine for Video, where you can just play the same frame over and over, it's NOT fine for audio where the buffer can simply go blank.

And then I realized an even WORSE problem: There is no separation between Video and Audio processing time! It's all done with ONE thread!! So while the Video is trying to decode / process the video effects, the audio can run out of data.

To solve this problem, we will use FOUR threads: Video In, Audio In, Video Out, and Audio Out. If one operation is blocked, it won't affect the others. Of course, if the video or audio simply run out of data we'll have to stay silent. But at least the Audio Input won't affect Video Ouput or viceversa.

Another problem is that using Mutexes can get things slow, specially for audio. I've been researching for a while about lock-free data transfer, and I remember one guy saying something about audio FRAMES.

What? O.O *blink blink* Frames in audio? O.O *blink blink*

That's right. By splitting the buffer into separate small frames of time (say, 1000 samples) we can use a fixed buffer of POINTERS to those frames.

This means: Instead of having this:

[..........................................................]

we have this:

A [.....]
B [.....]
C [.....]
D [.....]
E [.....]
F [.....]
G [.....]
H [.....]
I [.....]
J [.....]

[ABCDEFGHIJ]

So a thread can reserve one of the N frames of audio for buffering, and instead of having to avoid touching a HUGE GODZILLA chunk of data, we can just meddle around with one of the little godsukis. And the list which tells which order they should be played, can be a lock-free list (this means it will have thread-safe algorithms which do not require mutexes or any of that.

Finally, with the lessons learned during the thread module's development, I can finally delete that awful sleep-based synchronization and start using semaphores and/or condition variables. I think I'll go for condition variables, as I can wake up the thread either when I need to send data, or when I need to stop it.

Edit (Oct 2,2008):

The actual redesign didn't use audio frames, after all. It was much simpler to use a circular buffer with one sample per slot.

Forward declarations: Not good enough?

2008-09-14T00:35:00.000-07:00

It's widely known by C++ programmers that replacing classes instantiations with class pointers in your classes, allows you to do a forward declaration in your headers and save compilation time.

Example:

Bad:


a.h:

class A {
};


b.h:

#include "a.h"
class B {
  A myvar;
}

Good:


a.h:

class A {
};


b.h:

class A;
class B {
  A* myvar;
}

Then, in the CPP you do the #include. But this is NOT enough! Since most of my classes are pretty brief, due to the fact that some are template instantiations, I have not only to include in each .cpp the headers for all the classes and ALL the classes contained in those classes ad infinitum. OK, If I followed the first approach I would only "include one file", but that's not the point, since that "one file" would start an include chain. So it doesn't matter what I do, in each .cpp I always end up invoking all the .h files and end up with a gigantic object file.

Let's see what this little code does:


#include "smap.h"
#include "avclip.h"
#include "avtransition.h"
#include "aveffect.h"
#include "aveffects.h"


AVClip::AVClip()
{
    //ctor
    m_Effects = new AVEffects;
    m_EndingTransition = new AVTransition;
    m_Markers = new SMapUintUint;
}

AVClip::~AVClip()
{
    //dtor
    delete m_Markers;
    delete m_EndingTransition;
    delete m_Effects;
}

why do I need to include all the headers JUST TO CREATE AN OBJECT? Because by doing "m_Effects = new AVEffects", I call AVEffects::AVEffects(), and for that I need the include file. Which also ends up invoking svector.h, which also includes serializable.h and . Eew!!

Enter forward declarations in the .cpp files!

To solve this problem, I created a class named AVClasses, which encapsulates object creation, deletion, serialization AND deserialization for ALL THE KNOWN CLASSES.

avclasses.h:


#include 

class AVSettings;
class FXParameterList;
class AVEffectParamDeclaration;
class AVEffectParamDeclarations;
// ...

class AVClasses {
    public:

        static void Create(AVSettings* &ptr);
        static void Create(FXParameterList* &ptr);
        static void Create(AVEffectParamDeclaration* &ptr);
        static void Create(AVEffectParamDeclarations* &ptr);
        // ...

        static void Delete(AVSettings* &ptr);
        static void Delete(FXParameterList* &ptr);
        static void Delete(AVEffectParamDeclaration* &ptr);
        static void Delete(AVEffectParamDeclarations* &ptr);
        // ...

        static std::string serialize(AVSettings* &ptr);
        static std::string serialize(FXParameterList* &ptr);
        static std::string serialize(AVEffectParamDeclaration* &ptr);
        static std::string serialize(AVEffectParamDeclarations* &ptr);
        // ...

        static bool unserialize(AVSettings* &ptr, const std::string& s);
        static bool unserialize(FXParameterList* &ptr, const std::string& s);
        static bool unserialize(AVEffectParamDeclaration* &ptr, const std::string& s);
        static bool unserialize(AVEffectParamDeclarations* &ptr, const std::string& s);
        // ...
};

This little toy hides the object creation, destruction and (un)serialization. Of course, the avclasses.cpp file will include ALL THE HEADERS. It's fun!

avclasses.cpp:


#include "avclasses.h"

#include "avsettings.h"
#include "fxparameterlist.h"
#include "aveffectparamdeclaration.h"
#include "aveffectparamdeclarations.h"
// ... etc.

void AVClasses::Create(AVSettings* &ptr) { ptr = new AVSettings; }
void AVClasses::Create(FXParameterList* &ptr) { ptr = new FXParameterList; }
void AVClasses::Create(AVEffectParamDeclaration* &ptr) { ptr = new AVEffectParamDeclaration; }
void AVClasses::Create(AVEffectParamDeclarations* &ptr) { ptr = new AVEffectParamDeclarations; }
// ...

void AVClasses::Delete(AVSettings* &ptr) { delete ptr; ptr = NULL; }
void AVClasses::Delete(FXParameterList* &ptr) { delete ptr; ptr = NULL; }
void AVClasses::Delete(AVEffectParamDeclaration* &ptr) { delete ptr; ptr = NULL; }
void AVClasses::Delete(AVEffectParamDeclarations* &ptr) { delete ptr; ptr = NULL; }
// ...

std::string AVClasses::serialize(AVSettings* &ptr) { return ptr->serialize(); }
std::string AVClasses::serialize(FXParameterList* &ptr) { return ptr->serialize(); }
std::string AVClasses::serialize(AVEffectParamDeclaration* &ptr) { return ptr->serialize(); }
std::string AVClasses::serialize(AVEffectParamDeclarations* &ptr) { return ptr->serialize(); }
// ...

bool AVClasses::unserialize(AVSettings* &ptr, const std::string& s) { return ptr->unserialize(s); }
bool AVClasses::unserialize(FXParameterList* &ptr, const std::string& s) { return ptr->unserialize(s); }
bool AVClasses::unserialize(AVEffectParamDeclaration* &ptr, const std::string& s) { return ptr->unserialize(s); }
bool AVClasses::unserialize(AVEffectParamDeclarations* &ptr, const std::string& s) { return ptr->unserialize(s); }
// ...

I took a look at the filesize of the avclasses.o. It measures 579K! Half a meg!

But now let's see what happens if I use AVClasses inside the previous AVClip.h:


#include "avclip.h"
#include "avclasses.h"

AVClip::AVClip()
{
    //ctor
    AVClasses::Create(m_Effects);
    AVClasses::Create(m_EndingTransition);
    AVClasses::Create(m_Markers);
}

AVClip::~AVClip()
{
    //dtor
    AVClasses::Delete(m_Effects);
    AVClasses::Delete(m_EndingTransition);
    AVClasses::Delete(m_Markers);
}

And the results are the following:

Before:

avclip.o: 105356 bytes.

After:

avclip.o: 33136 bytes.

Needless to say, compilation is almost instant!

Yes, there is a drawback to all this. That extra call when creating the objects. But if we look at the AVClasses code, it's more like a jumptable, except for the serialization stuff, which would duplicate all the memory transfers. But that can be solved by simply modifying the code to pass a string by parameter instead of returning a string.

So we save a lot of duplicate code in the object files for a tiny runtime penalty. Is it worth it? WAY YES!!!

When I finish changing all the code in my files I'll tell you how much the compilation time disminished.

Update: After changing lots of files to se this approach, I noticed that the gain in compilation time is only marginal. I wonder if the change is really worth it.

Update (Sept 15, 2008): I finally realized that this is nonsense, it's not worth it, and just stupid. Also, I also made another realization: The current STL-based model is optimal in complexity. I may not like the STL bloat, but the fact is that it keeps programming SIMPLE. I don't need t ocomplicate myself with more pointers and implement lots of "exceptions-to-the-rule" routines.

So I reverted my SVN copy to the one before these changes and kept going. However, it was a good experiment to make, and this way I won't have to worry with yet another "what if I had..." thought. Now move along.

Threads module FINISHED! (for real this time)

2008-09-11T07:02:00.001-07:00

After moving all the private data to the CPP, cleaning up the API (that means it's stable now, unless I add new functions) and fixing a few things, I'm glad to announce that the Threads module is Finished!

It costed me many hours of sleep, many e-mail exchanges with linux kernel experts, but finally, it's done.

Now, back to the playback framework.

Con Kolivas answers: Yield() is bad. VERY bad.

2008-09-10T14:39:00.001-07:00

Con Kolivas, the mind behind the new Linux scheduler, answered a simple question for me.

It's the same Sleep() vs. Yield() issue that has been debated for ages, but this time we've already discarded sleep, so the question was more Yield() vs. wait.

Question: What should I use to put a thread to sleep for a limited time if there's no work to be done? A semaphore, or a yield?

Answer:

Yield just drops the cpu for other processes and threads to go first. It does not specify who should go next, how many processes should use cpu next, nor does it say when to return. Let's say you yield and one nanosecond later the work is available. On a loaded system it's theoretically possible to yield for up to 10 seconds. That's 9.99* seconds too long that you've yielded. Alternatively, if the thread yields for .5 seconds and the work is available
at .6 seconds, the yielding thread comes back and there is no work available, that thread now wastes cpu uselessly, checking for work and just yielding again for however long.

With semaphores, you rely on the work actually being available before waking up the thread. There is no wasted cpu at all, and the thread is signalled very fast that it should now wake up.

It takes more effort to keep track of where you've put your semaphores, who's waiting on what and so on, but in the long run the results are potentially much better. How big the gain is depends on how parallelisable your workloads are. Nonetheless, wasting cpu doing nothing when there is a signal mechanism to only wake things when there's work available is much better.

Con

Thanks a lot, Con! Now onto rewriting that userspace mutex again... *sigh*

--
Update: I forgot to thank Joseph Seigh of atomic-ptr-plus, he was the one who suggested using a semaphore in the first place.

Mutexes revisited; Scheduling questions.

2008-09-08T23:42:00.000-07:00

I finally completed implementing the sySafeMutex class.

My locking routine was something like this:

bool SafeMutex::Lock() {
bool success = false;
while(!success) {
 success = TryLock();
 if(success) { break; }
 if(aborter && aborter->MustAbort()) return false;
 Sleep(1); // Sleep for one millisecond
}
}

The problem is that if in that sleep time the other thread uses the mutex, then we fall in a problem called Resource starvation; The thread that begins to sleep never gets the mutex because other threads get the lock while the sleeping thread missed it. So instead of sleeping for a huge millisecond I only sleep for one scheduling cycle:

bool SafeMutex::Lock() {
bool success = false;
while(!success) {
 success = TryLock();
 if(success) { break; }
 if(aborter && aborter->MustAbort()) return false;
 Yield(); // Sleep as little as possible
}
}

But the problem of resource starvation still threatens us; So what can we do? I added a tight loop that tries to lock the mutex for the first 30 iterations. A tight loop when trying to lock a mutex is called a spinlock. Spinlocks are very CPU-inefficient (they consume too much CPU), but if they're combined with sleeping, they make things more balanced.

bool SafeMutex::Lock() {
bool success = false;
unsigned i = 0;
while(!success) {
 success = TryLock();
 if(success) { break; }
 if(aborter && aborter->MustAbort()) return false;
 if(++i>=30) {
     i = 0; Yield();
 }
}
}

Now I thought: Let's make the last thread that used the Mutex wait more the next time:

bool SafeMutex::Lock() {
bool success = false;
unsigned i = 0;
bool waspenalized = false;
while(!success) {
 if(!waspenalized && m_LastThread == GetCurrentThreadId()) {
    Yield();
    waspenalized = true;
 }
 success = TryLock();
 if(success) { m_LastThread = GetCurrentThreadId(); break; }
 if(aborter && aborter->MustAbort()) return false;
 if(++i>=30) {
     i = 0; Yield();
 }
}
}

By penalizing the last thread who got the mutex with an additional Yield(), we avoid the situation of one thread getting the lock all the time. Unfortunately, this adds an unnecessary yield() every single time we try to get the lock!

After I studied more, it turns out that mutexes, semaphores and all those synchronization primitives rely much more on thread scheduling than on simple tricks. For example, a Semaphore puts the first waiting thread next on the line for execution - this goes way beyond simple user implementations. But for our purposes, I think the proposed implementation (without the yield) will suffice.

Update: I finally figured it out. Instead of penalizing the last winning thread BEFORE trying to lock the mutex, penalize it AFTER trying to lock it. This way, the other threads will try to spinlock the mutex, while the last winning thread will be sleeping. Let's extend that to the TWO last winning threads, and this is what we get:


bool sySafeMutex::Lock(syAborter* aborter) {
    bool result = false;
    unsigned int i = 0;
    unsigned long id = syThread::GetCurrentId();
    for(;;) {
        result = TryLock(aborter);
        if(result) { break; }
        if(aborter && aborter->MustAbort()) { break; }
        // Scheduling strategy:
        // After the first try, the last owner loses its chance of winning;
        // After the 5th try, the previous-to-last owner loses its chance of winning;
        // After the 50th try, all threads get the same chance of winning.
        if((i >= 50) || (id==m_LastOwner) || (id==m_LastOwner2 && i >= 5)) {
            syThread::Yield();
        } else {
            ++i;
        }
    }
    return result;
}

void sySafeMutex::Unlock() {
    unsigned int id = syThread::GetCurrentId();
    if(m_Owner == id) {
        if(m_Recursive && m_LockCount > 1) {
            --m_LockCount;
        } else {
            // Set m_LockCount to 0.
            m_LockCount = 0;
            m_LastOwner2 = m_LastOwner;
            m_LastOwner = id;
            m_Owner = 0xFFFFFFFF;
        }
    }
}

The RAII parttern; Sentry classes

2008-09-08T05:39:00.000-07:00

I just found an amazing article on a seemingly unknown pattern in programming: RAII ( Resource Acquisition Is Initialization).

Basically, it is a class whose constructor initializes some resources, and whose destructor frees them. This prevents problems such as memory leaking or keeping a file locked when an exception occurs.

The concept can be generalized into "Sentry Classes". These classes perform an action on construction, and on destruction they clean up.

I had wondered what would happen in one of my classes if something had raised an exception (code has to be exception safe, did you know?). We already had prepared for locked mutexes on exceptions with the class wxMutexLocker (or in our case, syMutexLocker, sySafeMutexLocker, etc).

But what about flags? In VideoOutputDevice, there's a flag called m_Playing that tells us whenever we're sending a frame to the output buffer. What happens when (not if) an exception occurs during that?


void VideoOutputDevice::LoadVideoData(syBitmap* bitmap) {
 bool result = true;

 {
     syMutexLocker mylocker(*m_mutex);
     if(m_playing || MustAbort()) {
         result = false;
     } else {
         m_playing = true;
     }
 }

 if(result) {
     LoadDeviceVideoData(bitmap);
    // EXCEPTION OCCURS! The code is aborted and
    // m_playing is never set to false! The whole class
    // is rendered useless.
     m_playing = false;
  }
}

Eeew. Looks ugly, isn't it? Well. Pay attention to the new, improved version using Sentry classes:


void VideoOutputDevice::LoadVideoData(syBitmap* bitmap) {
 sySafeMutexLocker lock(*m_Busy, this);
 if(lock.IsLocked()) {
     syBoolSetter setter(m_Playing, true);
     LoadDeviceVideoData(bitmap);
 }
}

What? That's it? Yes!! The sySafeMutexLocker tries to lock the safe mutex m_Busy. If successful, we set the m_Playing flag to true, and then proceed to Load the Data from bitmap.

Whether or not an exception occurs in LoadDeviceVideoData, the setter is destroyed, setting m_Playing to its old value (which is false), and on the function exit, the safe mutex m_Busy is unlocked.

Here's the code for syBoolSetter:

/** @brief Class that sets a flag to a specific value during its lifetime. */
class syBoolSetter {
 public:
     /** Constructor */
     syBoolSetter(bool& flag,bool newvalue);

     /** Destructor. Sets the flag to its original value. */
     ~syBoolSetter();
 private:
     bool& m_Flag;
     bool m_Old;

};

syBoolSetter::syBoolSetter(bool& flag,bool newvalue) :
m_Flag(flag) {
 m_Old = m_Flag;
 m_Flag = newvalue;
}

syBoolSetter::~syBoolSetter() {
 m_Flag = m_Old;
}

Simple, effective and elegant.

New addition to threads module: Atomic Operations.

2008-09-07T17:08:00.000-07:00

I realized that I could simplify a lot of code in the Saya Core by replacing some mutexes with atomic operations. I decided to encapsulate them in a class named syAtomic. This makes Saya now requiring not only GCC compatibility, but also a 486 or greater CPU (I added -march=486 to the compiler flags). Given the fact that most CPU's right now are Pentiums (and you'd certainly need a Pentium for video editing :P ), i'm sure there will be no problem with this.

Regarding the simplification, here's an example: the VideoInputDevice class has a flag called m_IsBusy, which it sets and unsets whenever it's doing an operation. I realized that for all intents and purposes, this was, in fact, a mutex (with an auxiliary mutex to lock access). I also realized that the only thing I did when waiting for m_IsBusy was to check if an abort signal was sent.

So I made my own class sySafeMutex (now possible thanks to the atomic operations), which, when a thread tries to lock it, instead of just waiting for the mutex to be unlocked, it periodically checks if an abort signal is sent (an syAborter* parameter is sent to the Lock() function). Additionally, I added another flag to optionally run the check in a tight loop for the first 3 milliseconds. This will avoid wasted CPU cycles if the only thing we want is to change a variable.

I'll also make more simplifications to the code of the a/v device classes. Stay tuned.

Threads module finished!!

2008-09-06T12:55:00.001-07:00

Whew. I thought I would never finish this behemot. It's still not tested and some things MIGHT not compile on Windows, but that can be fixed with a tiny bit of code revision.

Later I'll decide whether to add support for atomic functions or not.
If anyone's an expert in multithreading and OS design, please help me debug this thing.

Decided to rely on GCC features.

2008-09-06T00:10:00.000-07:00

At first I wanted the project to be compilable by any compiler, but I have decided to stick with GCC (which is cross-platform, anyway), for two reasons:

1) GCC provides 64-bit integers for C++, which I need for the timeline.
2) It provides atomic operations, which are VERY useful for efficient multithreading programming.

I won't say more, since it's kinda late and I need sleep. Good night.

Lock-free algorithms part 2: CAS

2008-09-03T23:03:00.001-07:00

Hello again. I'll finish this lock-free programming with three links:

The first link is the Compare-and-swap atomic operation. It's atomic because most processors already have an instruction for it. Nothing can be more atomic than one cpu-instruction :)

http://en.wikipedia.org/wiki/Compare-and-swap

In computer science, the compare-and-swap CPU instruction ("CAS") (or the Compare & Exchange - CMPXCHG instruction in the x86 and Itanium architectures) is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple boolean response (this variant is often called compare-and-set), or by returning the value read from the memory location (not the value written to it).

CAS is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms. Maurice Herlihy (1991) proved that CAS can implement more of these algorithms than atomic read, write, and fetch-and-add, and that, assuming a fairly large amount of memory, it can implement all of them ^[1].

The second link is an article from Dr. Dobb's journal implementing a the aforementioned Hazard Pointers.

http://www.ddj.com/cpp/184401890

And finally, an algorithm from AT&T research to implement STL-compatible (well, more or less) vectors using Hazard Pointers:

http://www.research.att.com/~bs/lock-free-vector.pdf

Enjoy.

Lock-free algorithms and hazard pointers

2008-09-03T20:45:00.000-07:00

And here I thought mutexes, critical sections, conditions and semaphores were all that would have to be learned about multithreaded programming. Turns out I was wrong.

It all began with a guy on irc.freenode.net (his nick was dshs) asking how to do inter-thread synchronization for a multimedia project (I invited him to join the team, but he politely declined). He said something about "lock free queues". So I wikipediaed it and here's what I read:

In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. "Lock-free" refers to the fact that a thread cannot lock up: every step it takes brings progress to the system. This means that no synchronization primitives such as mutexes or semaphores can be involved, as a lock-holding thread can prevent global progress if it is switched out. "Wait-free" refers to the fact that a thread can complete any operation in a finite number of steps, regardless of the actions of other threads. All wait-free algorithms are lock-free, but the reverse is not necessarily true. An intuitive way of understanding the difference between wait- and lock-free algorithms is that a thread executing an operation of a lock-free algorithm may not be impeded if another thread's execution is prematurely halted, whereas if the algorithm was wait-free, the first thread may not be impeded even if the second thread is aggressively interfering with the shared state.
Lock-free algorithms are one kind of non-blocking synchronization.

As I kept reading, I learned that algorithms for lock-free stacks, queues and even vectors are already out there. It means that you can read and write all the stuff you want in a multithreaded environment, without having to use a single semaphore, mutex or condition. Wow.

And that wasn't all. I just learned that a NEW algorithm called "Hazard pointers" was created for non-blocking synchronization, in 2004.

So here's the description of a Hazard Pointer, right from Wikipedia:

In a multithreaded computing environment, a hazard pointer is an element used by a methodology that allows the memory allocated to the nodes of lock-free dynamic shared objects to be reclaimed. Using the methodology, each thread keeps a list of hazard pointers indicating which nodes the thread may later access. This list can only be written to by the particular thread but can be read by any thread. When a thread wishes to remove a node, it places it on a private list and periodically scans the lists of all other threads for pointers referencing that node. If no such pointers are found the memory occupied by the node can be safely freed.

This was JUST four years ago! It's a revolution that could be comparable to fast genetic sequencing, and I'm only learning about it right now! Where have I been these years? Oh, right. Working.

If you want to know more about Hazard pointers, you can read the Hazard Pointers Full Article (PDF), courtesy of IBM Research.

I don't know if this will be of use later for Saya, where we'll have to quickly deal with low-latency stuff. Probably I may need it for later.