Few Words For the Trees

Reimplementing red-black tree data structure, which exist in WINGs, but heavily underused, I've found one funny optimization. Everyone is starting with classical rotate_left and rotate_right functions, and they're updating root node on every rotation. That causes more checks and assignments than required in some cases. Solution is simple as always: tree rotation functions can be simplified by factoring out code for setting root node.

I must admit that this particular code is pretty good in WINGs. There's only a little space for improvement. And it makes me wonder why those beautiful trees weren't used for example in implementing hash tables. Hash tables in WINGs are simple arrays of pairs, and it's really possible to speed them up a lot.

I'm looking at savannah. It's most likely, that I host nexmaker project there.

New Memory Layout

I have «invented» new memory layout for objects. Now creating new objects as well as wrapping simple data in object is very simple. The solution is to keep internal fields at negative offsets. The nm_object function returns pointer inside allocated block, and nm_release is able to find free and destroy methods out of this pointer. Additionally, deallocation of memory and destruction of object is now two different configurable operations. This allows me to create objects on stack or using ob-stacks or any other memory manager.

Working with objects is really simple now. I'm having fun with hacking nm again. :)

Wrong Way

Seems like I stepped on a wrong path. Things are getting too complicated. I'm not ready to support full objects hierarchy in plain C. I don't want a lot of automatic actions. The code should be much simpler.

Some things learned from what have been done are useful. I'll keep the experience and continue hacking source in some other way. It's time to think. :)

New API Structure

As I already noted, I have played a little with valgrind and kcachegrind, and measured some new code against ideal, hand-written code. The first thing I noted is amount of time spent in malloc and free functions. Another thing is that time spent in single wrapper function became significiant when that function is called about millions of times. Let's look closer at WMCreateObject function. It is simple wrapper over malloc with few checks. In the nearest future this function will be called everywhere. Why not make it inline?

Another issue, that eats time on many calls is checks for null-pointers. I don't like the idea of terminating application once I got out of memory. It's application's job to decide what to do. Construction functions return NULL if memory allocation fails. If it doesn't fail they're filling allocated memory with some data. And those checks are really taking time. Generally I don't need more than one check for single object construction call.

The solution I came is to divide API. Internal API will be set on small, mostly inline functions, mostly without any checks. This doesn't mean it would call malloc and than unconditionally write something in returned pointer. Memory allocation and filling object with data is just different functions. With this structure I will be able to allocate memory, check for NULL, and call multiple filling functions without penalty for additional checks.

Naming Conventions

I'm changing the project name. The name WindowMaker will be held by original project. It's possible that original development team will wake up at some day and produce something. I doubt that they will, but it's possible anyway. Since I'm practically forking original project, it's good idea to change the name. NextMaker seems like a good name for my project. I thought it out in times of first attempt to fork, and I think, I'll keep it now.

Now, to the style. I don't like pascalish names used everywhere in WindowMaker. I'll make them all lowercase and with underscore as word separator. The shorter name is better the longer one. Prefix change reflects change in project name. Now all function names will start with «nm» instead of «WM». Prefixes and suffixes of names will have some meanings: «nm_» stands for ordinary exported functions, «nmi_» is for internal functions, which is usually inlined, «nmt_» is for type-tags in object system and so on. For example WMReleaseObject function will become nm_release after change, and WMString will be nmt_string.

I won't do that all at once. Changes will be made only in parts of code I'm touching. There's also some plans on changing file layout and structure of API, but those are things I'll think about a little bit later.

WMArray vs. WMList

Yesterday I have analized sources of WINGs and WindowMaker a little. Now I'm certain that WMArrays are mostly misused. Little research showed that the most used pattern of accessing data in arrays is plain iteration form beginning to end. There are only four exceptions (out of approximately 23 use cases), where random access to data is used: WMList, WMPopupButton, WMSplitView, and switch panel. And I don't think that all of those can't be converted to using linked lists and be more efficient. Moreover, linked lists are actually used in many places in WINGs. For example, event handlers are organized in lists, notification observers are also organized in lists.

I'm not talking here about blind replacing of all arrays with linked lists, it would be stupid. But if I feel that linked list is more appropriate structure for particular task, I'll use it. If I see, that some linked list is implemented ad hoc, I'll replace it with WMLList data structure. There's possibility that after removal of WMPropLists, WMLLists will take place of proplist arrays.

Since the name WMList is already taken by list widget, I will use the name WMLList for data structure. I will probably change all names later anyway. Now I'm implementing WMLList object as double-linked list. If there will be never the need to iterate those lists in reverse direction, I'll remove second pointer, but currently I think this small memory overhead will pay off shortly.

Strings Handling

The idea is to keep length of string together with characters, just like in old WMData structure. In first attempt I allocated buffer with second call to malloc and stored only pointer to character buffer in the object. Then after playing a little with profiler I've changed code to use flexible array for a buffer. That also eliminated the need for WMString-specific destructor. Now I have a function WMCreateString which does basically the same as wstrdup (and a little more, because it at least keeps length of the string), but performs about 10% faster.

The other thing I will certainly need is some function to concatenate mupltiple strings. This function will replace wstrconcat, wstrappend, and also sprintf in many places. What I don't like about existing functions is calls to realloc. It is much better to collect strings to be concatenated in some kind of container like array or list, calculate length of the resulting string, call malloc and copy all data int new string. It would be also good in some situations to have function with variable argument list, that concatenates all its arguments.

I have even more ideas for handling strings. For example it may save a lot of CPU time if there will be string objects that doesn't copy literal strings when it's not absolutely needed, and keeps only pointer to it. Or it could be wise to create objects to represent substrings. They will keep reference to original string, offset, and length. Now I have ideas for at least four differend kind of strings. I think it is a good time to start experimenting with subobjects which will have more methods than just destroy.

Object System Issues

I have actually started hacking new object system for WINGs. The first thing I have noticed is that I don't want type tags to be dynamically allocated. It's very unclear when to destroy and free memory of such dynamic objects. Pointers to statically allocated objects should work as well.

It was excellent decision to start writing tests. The first thing I stepped on was dynamic type tags, and the second was lack of inheritance in C. WMRetainObject and WMReleaseObject functions now accept pointer to void type as argument as most generic type of pointers. There is no way to specify that function accepts pointers to objects only derived from WMObject structure. Now it is at least possible to use these functions without explicit type casts or some other ways to converting types.

I thought about where to start actually replacing current WINGs' objects with newer ones. It won't be PropLists. PropLists will be replaced almost at the end, just before I'll start hacking widgets. It won't be any of container types. All of them will be replaced little later. First two candidates for replacement is WMData and... strings. I choose to start with strings.

Testing

Nobody will argue that code needs testing. Testing can be performed in numerous ways. Sometimes testing is not enforced by project conventions (which happens at work mostly, because no-one is willing to spend time to create something that don't provide any cool features). In those projects I usually create bunch of files named a.c, b.c and so on in a root directory of a project. These are «tests». I compile and run them by hand. I never commit those files, and often forget what are they for. I'm always afraid to delete them by some mistake.

In my home projects I have a freedom to do whatever I want, including writing «useless» code solely for testing purposes. And I feel good. Whenever I want to know if my recent changes break something I can type «make sure» and check that everything is ok (or not ok :) ). I would like to do such things with WINGs too, but no-one before me cared to write any tests for WINGs. Few small programs in WINGs/Tests directory can't be counted as real tests. They're just like my ?.c files in projects at work with one small exception: they are commited in cvs.

I use cunit package to test the code written in C and valgrind to detect memory leaks. Usually, I just run cunit program under valgrind. I'm starting writing tests for parts of WINGs I touched. Tests won't be compiled by default. I don't want to force everybody to install cunit at their systems. To start testing go to WINGs/Tests directory and type «make sure».

Reference Counting and Objects

While I was looking at WINGs/memory.c eliminating malloc wrappers, I've found two functions that drew my attention. It was wretain and wrelease. If I'm not mistaken, the original idea was to eliminate all handcrafted reference counting code into one place. This is definitely the Good Thing™. But current implementation just sucks. Using hashtables for storing counters with pointers as a keys is definitely not my way of thinking. And those functions are used only in small number of objects in library, with handcrafted reference counting functions for all other objects.

Let's go into that problem little deeper. WINGs library does have objects. In fact there's at least three kind of objects, with different ways to distinguish types:

• «raw» data structures like WMArray, WMBag etc with no way to determine type;
• PropList-wrappers over raw structures with closed set of type tags;
  
• widgets with open set of type tags, but with rudimentary support for creating new type tags.

Some of these objects use generalized reference counting and some not. That makes total of six potential object systems with five of them actually implemented. I don't understand why there should be more than one object representing one thing, moreover if those objects have different APIs. I don't understand why there should be more than one object system in single library.

I think I'll replace this object's zoo with something better. I came up with the following idea. Two common fields for all object are almost obvious. These are some kind of a type tag, and a reference counter for that object. The best kind of type tag I can think of is a pointer to a structure with pointers to methods as fields. I'll start it with the single destroy field, which if present will handle additional operations needed to destroy an object. This solution may add just a little overhead to some «raw» objects, and no overhead to all others. They're already have something like counter field, type tags or destructor field. This overhead should pay off when I start replacement of PropLists with new objects.

MALLOC Wrappers Is Bad

I have found my old messages to wm-core@w.o mailing list. I have to admit that I still agree with most things I've said then. I still think that no library function should print something on the screen unless this is the main goal of the function. As the only exception to this rule I can accept some debugging output I can disable. I remember how much trouble was working with libxml2 which prints various warnings about malformed xml being parsed with no way to disable this. Exactly the same things I think about termination of applications within the library function. I prefer that these decisions should be left for application.

I thought about using Boehm garbage collector library. There's even some experimental code in WindowMaker to use it. It looks like a very appealing idea for a lisper like me. But garbage collectors are generally incompatible with tools like valgrind. And I want to use such tools, at least until I clean up the code. Also, using some garbage collecting library can possibly happen to be incompatible with some future changes like embedding extension language such as guile, which uses own garbage collector.

I decided to eliminate wmalloc, wmalloc0, wrealloc, and wfree functions. Checking return value everywhere malloc is used and reacting gracefully to that condition requires huge amount of work. It will take some time, and probably will be the cause of many other changes. I'll do it in a number of small steps.

Quest Description

WindowMaker is dead. Admit it. Website is half-alive, cvs is down, mailing lists are down, last release was more than two years ago. About three years ago, in previous stale period I have tried to start hacking it. The results were creation of new development team, creation of WM2 branch, and new release of main branch. Now the project staled again for a long time already.

I'm starting hacking it again. This time I work alone, privately, without any team. I am doing this for my own amusement and I fell free to change anything I want, even if what I change is a minor, unimportant, or low-priority improvement. I have source of the last release, and the cvs snapshot I was able to catch before servers went down. I don't care for «official releases», but at some point I'll make my git repository publicly available. I don't accept any patches. I don't want your code, please don't spoil my hacking fun. :) But I would be thankful for ideas and code reviews.

This blog is attempt to document the way I was thinking while changing code. Everyone can check what was changed, and how it was changed using version control tool. With some discipline from committer, it's even possible to see why something was changed. I thought that writing a blog can be a good way for describing decisions not directly affecting the code. And it can show what I was thinking about when decided to make some change.

Tags are filenames in repository. May be I will use some additional tags when appropriate. When my git repositary go public, I'll write commit ids to related postings.