Wednesday, September 29, 2010

QubLib Multithreading

This past week was a career fair at Brigham Young University, and so I went and decided to distribute a few resumes. There were the big companies like Microsoft, Apple, Adobe, and others like that, and so I took the chance to drop my name into all of their employment databases. On my resume I have a quick snippet about QubLib. It really isn't all that much, but it is a small bullet point that says that I'm developing a Cross-Platform C++ Library that supports common Data Structures, Networking, Shared Strings, and Multithreading. Multithreading, huh? After the career fair I went back and looked at how far I had gotten on Multithreading in the past month. Not too far. The Windows Thread class could start a thread, but waiting for finish/joining, suspending, and resuming were all features that were on the to do list. Fortunately for me, a week after noticing this I got sick (yesterday), and so what else was I supposed to do while I was sitting in bed all day? I worked on Cross-Platform multithreading. :) So, now QubLib fully supports an inheritable Thread class that can start and wait for finish, a Mutex class, and a Semaphore class. There was a particular joy that swept through me when I got the test cases to work on both Windows and Linux. Fun fun.

Thursday, August 5, 2010

QubLib Distributable

Well, I've been working hard for the past while on QubLib, and today was the first day that I actually build a distributable version. Unfortunately, just because I can build one now, doesn't mean I'm going to distribute it, but it's in the works.

I also just finished working on QubLib Strings. It was a really good experience working on them. I ended up deciding to make them the shared strings like I talked about in an earlier post. They're pretty nice, and hopefully the experience will not have just been for learning purposes.

Monday, August 2, 2010

QubLib Strings

Strings have been giving me a little bit of a challenge lately. Programming them hasn't been the problem. The problem has been deciding which type of design I want to use.

I've been told that Java uses a design that I will call "Shared Strings". Essentially, if you create the string "hi there" and then somewhere else you create it again, both string references are pointing at the same "hi there" in memory. This is extremely useful in situations where you have 10 bazillion references to "hi there". There is no need to have that same string 10 bazillion times in memory. However, doing it this way does produce a slight overhead problem. I have a StringManager singleton object that keeps track of all of my strings along with how many times they are referenced, very similar to my smart pointer that I introduced a while back. Everytime you create a string, it takes about a log(n) time chunk to see if the string is already in the StringManager. Then upon deletion, it takes another log(n) time chunk to see if the string has any other references. The deletion time is because in an actual String object I am storing a char*, which points to the actual heap-allocated character array in the StringManager. I suppose I could have a String object point to the char* and the integer value that indicates how many references it has. But keeping it the way it is right now is nice because it keeps things simple. What do you think? Are there any other options that I haven't considered yet but should keep in my head? Or, are there other factors that I'm not thinking about that would probably seal the deal for which route I will end up taking?

Thursday, July 29, 2010

QubLib Events

No, I'm sorry. This post is not about a pancake breakfast in honor of QubLib. It's not that type of event. This is about Event objects in associated with Event handling. For the past few days I've been working on getting these objects working and also in getting them tested. The result of my sweat and tears (mostly tears)?

Event0 e;
e += FunctionPtr0<void>(someFunction);

That little bit of code just set up an event, adding a pointer to the function someFunction, and then executed all functions that had been registered with the Event e. It may not be as pretty as I had envisioned it a couple of weeks ago, but it works. At the end of the day, that's what makes me happy.

Thursday, July 15, 2010

QubLib Application Class

One thing that I never felt good about with Qt was the idea of the QApplication class. For some reason I just felt like that should be a given. When I create a Window type object, shouldn't the system just know that I want all of my system messages to come through that Window object? At this point I feel it is important to state that I am by no means a Qt, Gtk, WxWidgets, Swing, or .NET UI guru. I don't understand all of the ins and outs of UI Design or the different constraints that are placed on UI Library developers from a desire to create Cross-platform libraries. It's my hope that someday QubLib will be in the list that I just mentioned, and maybe when it is being used, I'll understand this problem a little better.

This morning I woke up with the idea that it is important for there to be such a thing as an Application class. My reasoning was that it isn't that hard to image a program that is executing in the background without a currently displayed window. If you're using a Windows operating system, I ask you to look in the bottom right hand corner of your screen. All those icons are actually programs running in the background. I also think of the QubVersioning system that I want to make someday, which will be a type of Svn/Cvs versioning system, but that it will all be done in the background so that you don't have to ask it to back up your changes. It will just do it. All of these are examples of background tasks. So, it makes perfect sense to me that I should have an Application class that does not require a visible window. Also, something that I thought of was a multi-windowed program, such as the one that is used commonly in Macintosh systems and in the Gimp paint editing tool. If anyone knows the correct term for this, please leave a comment so that I can learn it. Anyways, that is a popular technique to use for programs that have multiple windows and I think it would be relatively easy to implement if there was an Application object that you just added Window objects to.

However, the issue that I mentioned with Qt earlier was that if I only want to have a single-windowed application, do I really need to create an additional Application object? Shouldn't I just be able to create a Window object and then tell it to Run()? So, somehow an Application object should be able to contain window objects, but then a Window object should have some of the functionality of an Application object... And, I would imagine that a Window object should be able to create multiple sub-Window objects. It sounds like there is an interesting inheritance design sort of thing waiting in this mess, but I'll have to think about it more later.

Friday, July 9, 2010

QubLib Smart Pointers Won't Be Quite As Smart

So, it's always a let down when you think you make a breakthrough on something just to find out that you forgot something that is vital to your development. My last post was about determining whether a pointer points to the stack or the heap. I thought I had found a way to determine this in a way that was independent to the hardware or OS of the machine, but when I tried it again on my Windows and Linux machines, I found that my Windows machine gave me some issues. My simple way of finding where the top of the stack is and then finding the direction it is growing in didn't quite work on Windows as I had hoped. So, I decided that I would try and have a function run before the main function is called (a constructor of a global variable), but then I thought that it won't be the exact beginning of the stack, because it is possible that another global variable constructor could be called that will point to an object that is lower on the stack than my variable that I was hoping would be the first variable on the stack. Grrr.... I was okay to live with that potential problem, but then I thought of one thing that just brought the entire concept crashing down. What would happen if I pointed a QubLib Smart Pointer at a static variable or a global variable? At this point, I realized I was attacking this problem from the wrong point of view. It's like trying to figure out whether a balloon is red by saying, "Is it blue? No huh? How about yellow? Purple? Lime Green? Neon Pink? ..." If you are trying to exhaust all of the possible things it is not just to figure out if it is red, then there will always be another color that you haven't thought of. However, if I could find a way to say, "Hey, is the ballon red?" or in my case, "Hey is this address on the heap?" then my problems would be solved. But, since I don't know how to do that, I guess for now QubLib Smart Pointers will just have to have a disclaimer: "Don't point at anything that is not in the heap. End of Story."

Thursday, July 8, 2010

QubLib Smart Pointers

Recently I have been really wanting to do SmartPointers in QubLib. This part of QubLib will only be operational in the C++ version of QubLib, because the Java and D versions will already have garbage collection, so they won't need SmartPointers. The way I chose to implement smart pointers is by having a templatized Ptr class that will act like any normal pointer. The only difference is that when this pointer is assigned to point at something, it registers what it is pointing at with a singleton PtrManager class. The pointer manager registers the address that the pointer points to, and then continues to keep track of how many Ptr objects are pointing at that address. When a Ptr goes out of scope, its destructor will be called, which will then indicate to the PtrManager that one less pointer is pointing at the address. If there are now 0 pointers pointing at it, the PtrManager will indicate to the dying Ptr object that it should clean up the address it points to. I didn't place the cleanup in the PtrManager because the pointer manager stores all of the addresses as void* pointers, and void* is undefined when you try to delete it.

So, I was really excited about my implementation, until I realized a large potential mistake: What if the smart pointer is pointing to something that is declared on the stack? It's not hard to imagine that happening. I create things on the stack and then give their address to a function all the time. Smart Pointers need to be smart enough to not delete something when it's on the stack, but yet be able to delete something when it is allocated on the heap. So, I looked around on the internet, but the only things I found on determining if an address is on the stack or the heap contained assembly code in them, and I didn't want to use assembly. I want QubLib to be cross-platform, so I decided that wouldn't be the way to go. I also found out that some stacks will grow towards 0 and some grow towards positive infinity. So, I created a new class called StackInfo that enables me to tell the direction that the stack is growing simply by creating two integers and checking to see which direction their memory addresses are progressing. After that I can tell if an address is on the stack if it is within the bounds of the top of the stack and the base of the stack. I don't know the base of the stack, but I can create an integer value that will be the top of the stack and I can use that with the stack growing direction to determine if the value is on the stack or the heap. I think this method works. I tried it on both my Windows 7 and Ubunto 10.04 LTS machines, but those are both running on the same processor. I wish I had a device with a different sort of processor that I could run these things on. Any suggestions? Like I said, last night it worked like a charm, but I'm curious what sort of pitfalls I would probably run into.

Tuesday, July 6, 2010

QubLib Function Pointers

So, this post actually comes from some things I jotted down a while ago at 2:00 AM when I couldn't sleep. Hopefully it makes sense.

It's about 2:00 AM and I can't sleep because I'm pretty sure this idea is keeping me up. It's not really that new of an idea. I'm pretty sure that sigc++ has already done it, however I think QubLib needs to have some sort of Functor object, or an object that encapsulates a function pointer. This would make function pointer usage EXTREMELY easier, and I really think it would open the door for Delegates (at least what I think delegates are). My idea of a delegate is a function pointer that points to a function of a specific instance of a class. Now, having delegates brings up the question of what happens when you have a delegate pointing at an object that has gone out of Scope? I'm still working on a pretty way to solve that problem, but the syntax that I'm thinking of is below:

int add(int num1, int num2);

// The three template types are a return value, the type
// for arg1, and the type for arg2.
FunctionPointer a(&add);
a(5,3); // returns 5

class A {
void Do();

A aObj;
// With a delegate, the first value is the type of the
// class that the instance will be. Then the same
// rules as above remain constant.
Delegate d(&aObj, &A::Do);
d(); // This will call aObj.Do()

I also think that with a system like this in place, Events would become not only possible, but much easier. In my mind, an Event would be an object that called a bunch of other functions, similar to signal/slot ideas in Qt. For example, if an object had an Event called Changed, and everything the object's internal data changed it would call the Changed Event, any object or function pointer that had registered with my object's Changed Event would have their registered function called. Internally the Event would just be a list of FunctionPointer objects. One of the keys would be that there would be an IFunctionPointer interface that had only two method declarations: the () operator and the Execute() method. The signatures would be correctly typed through templates, so the compile-time type checker would ensure that correct function pointers were assigned to correct Events. Also, with the interface in place, you could have a normal function and a method of a specific object register with the same Event, because they would both implement the same interface. I'm excited to work on this one.

Friday, July 2, 2010

Sorting List Interfaces

Qub Library is a cross-platform C++ library that I'm developing for my own uses, but also so that I can learn C++ and cross-platform principles better. This library has built in data structures, that I am already enjoying using. One of the common interfaces to the data structures I am using is the IList, which is just a random-accessible structure. One key thing about random-accessible structures is that they are generally sortable. The thing I've been thinking recently is whether the Sort() function should be a part of the data structure or whether it should be an external function that operates on the data structure. The way I currently have things set up is that there is an Algorithms::ShellSort() or Quicksort() method that takes a pointer to an IList object. I also have an IList abstract method that will sort the IList, but all it does on the inside is calls the Algorithms::ShellSort() function. While this is useful, in C++ it means that anything that could be placed into an IList must implement the "<" operator, which is the standard way of comparing two items in the list. This doesn't sound so great to me, because not only is that just another method I have to implement in my classes, it also won't make sense to certain concepts. What if I have an IList of thread pointers? Or function pointers? There are probably ways to order those types of objects, but if that isn't part of your initial design, why should a developer have to put those operators in? So, I think I'm going to remove the Sort() method from the IList interface and just leave it in the Algorithms static class.
This small example is an example of the question whether classes that hold data should have methods that operate on the data, or should there be other classes that manipulate the data. i think the answer to that question rests in the question: "What are the different ways that the data can be manipulated?" Take sorting a list for example. There are almost countless algorithms for sorting a list, whether it be a BubbleSort, Shell/SelectionSort, QuickSort, MergeSort, HeapSort, etc. If a sort method was implemented on a particular list object, then to keep these different options available you would have to pass a Sorter type of object that is given a list and an object that compares two elements of the list. This simple double-dispatch method provides the options that we wanted, but it is at the cost of having to add a parameter to the Sort() function. However, maybe that really wouldn't be so bad. I suppose it may just be a matter of style and taste.

Thread Safety

I've been thinking about the idea of thread safe data structures lately, and I've been a little torn. On one hand, I would think that all data structures should be thread safe in a reader/writer fashion, but on the other hand, some people are bound to complain that they don't want to lose clock cycles over synchronization when their program is only a single thread. That isn't really all that big of a deal to me (now anyway), but the thing that is annoying to me is that if all data structures are thread safe, then according to my principles of ease of use, all data structures should document that they are thread safe. I guess that's really not an issue though, because whether they are thread safe or not will have to be documented. I guess the real problem is that people should have options. They should have a choice. If everything is thread safe by default, then they have no choice on the matter. So, my thoughts have been that I would create an overloaded function called ThreadSafe(). This function would take in a bunch of different overloaded parameters, but the basic functionality would be that you pass a data structure to the ThreadSafe function, and then it would wrap and IThreadSafe decorator to the class. Of course I'm sure the naming will change, but this would significantly reduce code in large inheritance hierarchies. After the decorator is applied, all access to the inner data structure would go through the decorator, allowing for synchronization to occur. It wouldn't be hard for the user of such a library to create their own overloaded ThreadSafe() functions, where they can pass in their own data structures and follow the same pattern, keeping synchronization consistent throughout the program. It isn't hard to imagine ThreadSafe number objects, strings, and other types. The user wouldn't need to state that the variable 'x' is a ThreadSafe object; the function wrapper says it for you. Also, if you did it this way, you would need one ThreadSafe class per interface, whereas if you sub-classed class 'Y' to be 'ThreadSafeY', then there would need to be one 'ThreadSafeY' type class for every concrete class that wanted to be thread safe.

Tuesday, April 13, 2010

Another semester gone by

I think it's strange that I always seem to post at the end of a semester. I wonder if I just get busy during the semester or something? Anyways, the end of a semester can only mean one thing: goals! This summer I plan on working on some fun things, not the least of which is my QubLib framework, which will be a cross platform C++ wrapper for Win32 and the Xlib system. This summer I plan on doing the Win32 part and then as I have time I'll get around the Xlib system. What can I say, I'm a windows developer, even if that does sound rather oxy-moronish to some people. Anyways, I'm excited for this summer and I hope that I can pump out some new things.
The motivation for creating QubLib was that I couldn't find a Graphical User Interface toolkit that really meshed with my personal beliefs. I'm not talking about religious beliefs, but I believe that GUI toolkits should be easy to use, which I suppose is a matter of opinion, but MY opinion is the one that really counts here, right?