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.