Blog Stats
  • Posts - 99
  • Articles - 5
  • Comments - 39
  • Trackbacks - 108

 

Monday, May 29, 2006

String to Int []

I apologize for the code not being indented , I am using word 2007 and no matter what I do it does not seem to want to indent properly (I have tried copy/pasting to notepad, you name it), if you know how to get this working please contact me. See picture of word version http://geekswithblogs.net/images/geekswithblogs_net/gyoung/4418/r_word.JPG

 

update I manually indented all of it but I am still wanting to know how to avoid this

 

Everyone seems to enjoy performance posts so …. I saw this question in the advanced .net group and found it fairly interesting.

I have a comma separated list of integer values what's the quickest way to turn this into a integer array.

 

Being the geek that I am I set off immediately to find out just how quick I could make an algorithm fly.

That said let’s start out with the most obvious answer, we will split the string and call int.Parse() on the string elements. We can use this code to benchmark our other results against.

 

static int[] Split(string _Numbers) {
  string[] pieces = _Numbers.Split(',');
  int[] ret = new int[pieces.Length];
  for (int i = 0; i < pieces.Length; i++) {
    ret[i] = int.Parse(pieces[i]); 
  } 
  return ret;
}

 

Next we will need some data to feed into the routine. I chose "1,2,3,4,5,6,7,8,9,10,121,1000,10000" as my testing data. Running through this data 1,000,000 times takes a total of 4.39 seconds on my system (in release mode). I think that we can do better than this!!

Using an old trick I figured that I would just make the string a char [] and iterate through it taking my current number and subtracting its char code from ‘0’ (it just so happens that ‘9’ – ‘0’ = 9 how convenient! Applying this methodology leaves us with the following code.

static int[] Iterate(string _Numbers, ref int _Count) {
  int[] buffer = new int[4];
  char[] chars = _Numbers.ToCharArray();
  _Count = 0; 
  int holder = 0; 
  for (int i = 0; i < chars.Length; i++) {
    if (chars[i] == ',') {
      buffer[_Count] = holder;
      holder = 0; 
      _Count++;
      if (_Count == buffer.Length) {
        int[] tmp = buffer; 
        buffer = new int[tmp.Length * 2]; 
        Buffer.BlockCopy(tmp, 0, buffer, 0, tmp.Length * 4);
      }
    } else {
      holder = holder * 10 + chars[i] - '0'; 
    }
  } 
  return buffer;
}

 

This code also has some oddities involved with it since it does not know initially the size of the int [] that it needs to pass back. In order to support this, it grows it’s int [] as it needs to (by doubling). This can be an expensive operation so avoiding it is best. Also since it is doubling its array, it has a new parameter Count which it uses to return the total number of elements in the array it returns (it may return a 32 element array that only uses 18 elements).

As for performance, the exact code above will handle the same data as our first test in <> .5 seconds on my machine with a buffer size of 4. Not bad 10% of our first try! To show the importance of the buffer though, if we make the initial size 16 the code finishes in .4 seconds!

There are still some areas we can optimize though. Keep in mind that this code is creating 1,000,000 char []. This is a pretty expensive operation, by using unsafe code we can avoid doing this. Here is the code

static unsafe int[] Unsafe1(string _Numbers, ref int _Count) {
  int[] buffer = new int[64];
  _Count = 0;
  int total = _Numbers.Length;
  int holder = 0;
  fixed (char* a = _Numbers) {
    char* c = a;
    while (total > 0) { 
      if (*c == ',') {
        buffer[_Count] = holder;
        holder = 0;
        _Count++;
        if (_Count == buffer.Length) {
          int[] tmp = buffer;
          buffer = new int[tmp.Length * 2];
          Buffer.BlockCopy(tmp, 0, buffer, 0, tmp.Length * 4);
        }
      } else { 
        holder = holder * 10 + *c - '0';
      } 
      c++;
      total--;
    }
  }
  return buffer;
}

 

Again we use the same buffering mechanism that we used on the last entry. The main difference here is that instead of creating a char [] we use unsafe code to iterate through the string. With a buffer size of 16, this code runs through the 1,000,000 iterations in .37.

In running these, many of you may notice that for small bits of data that the iterate function may actually run faster than the unsafe code. This can be the case but as you add more data, the gap will grow larger in the favor of the unsafe code (it also uses less memory as it does not duplicate the memory from the original string).

Use the framework Luke!

We have had one problem thus far with our code, its ugly. Having to get back an array then use a separate counter from the length of the array to loop is .. well ugly. As an example consider the following.

int foo = 0;
int [] values = Iterate(numbers, ref foo);

for (int i = 0; i < foo; i++) {

}

//CANT DO

for (int i = 0; i < values.Length; i++) {

}

 

Personally I prefer the second way of doing this was it makes more sense to programmers. Luckily generics in the framework can do just this for us. By changing our return type from an int [] to a generic list we can keep most of the speed and offer a better interface.

static unsafe List<Int32> UseGeneric(string _Numbers) {
  List<int> ret = new List<int>(64);
  int total = _Numbers.Length;
  int tmp = 0;

  fixed (char* a = _Numbers) {
    char* c = a;
    while (total > 0) {
      if (*c == ',') {
        ret.Add(tmp);
        tmp = 0; 
      } else {
        tmp = tmp * 10 + *c - '0';
      }
      total--;
      c++; 
    } 
  }
  return ret;
}

 

This is a much nicer interface than what we had before and is still very performant. 1,000,000 iterations with this takes approximately the same time as out unsafe example! The reason this works about the same as our first example, is because it does pretty much the same thing internally with it’s buffer as what we were implementing on our own (of course, it does a much nicer job encapsulating it than we were so this is probably the best overall solution). Basically as you add items, it also doubles it's internal array size then copies over the old data in order to allow you to continue adding data.

 

Another solution which was offered up in the discussion by Ernst Kuschke is syntactical sugar (although not very performant) so I figured it was definitely worth including simply for its elegance (and it should probably be a good general method for doing this. Sugar like this is always more maintainable, converting this to support doubles or another type would be a lot easier than our other examples.

public static int[] doTheThing(string commadelimitedInts) {
  return Array.ConvertAll<string, int>(commadelimitedInts.Split(new string[] { "," }, StringSplitOptions.RemoveEmptyEntries), new Converter<string, int>(intToString));
}

public static int intToString(string strInt) {
  int i;
  int.TryParse(strInt, out i);
  return i;
}

Ernst takes advantage of the ConvertAll method to produce a very short bit of code that does the task. It has performance characteristics similar to our baseline as well (while being significantly shorter). If performance is not you main goal (it is quite rare that we are doing millions of theses transforms in an application), this is definitely the way to go as it is quite maintainable.

Update: Ernst's friend Piers came up with an even more elegant method of calling this

public static int[] doTheThing(string commadelimitedInts) {
  return Array.ConvertAll<string, int>(commadelimitedInts.Split(new string[] { "," }, StringSplitOptions.RemoveEmptyEntries), new Converter<string, int>(System.Convert.ToInt32));
}

The elegance of this solution is definitely apparent!

Now to put our various solutions to the real test I have made a big string [1..1000] that we will run through 1,000,000 times. All algorithms that use array growing will be seeded with an initial buffer size of 64 to make things fair between them while also forcing their weakness of having to grow the buffer a few times.

Algorithm

Execution Time

Split (Base Line)

00:05:42:703

Syntactic Sugar with Delegate

00:06:36:703

Iteration

00:00:22.312

Unsafe

00:00:16.90625

Unsafe with generic return

00:00:18.937

 

Analysis

As you can see performance for our base line (simple split) and the delegate method completely degrade under larger values as one would expect. As I mentioned earlier, the unsafe methods squeaked ahead of the iteration due to not having to create the char array. Of course, the real winner here is the generic return coming in second who makes our code readable, and extremely fast.

Can you come up with an algorithm for this problem? Post it here!

 

 

posted @ Monday, May 29, 2006 9:56 PM | Feedback (11)

AOP with Generics Thoughts

As some of you may have realized, I am in the process of re-implementing my AOP framework to fully support generics right now (figured I might as well as I am white boarding it for open source deployment anyways). I have come across numerous issues in dealing with generics. Today I sent an email to the castle project group (who are going through a similar task in supporting generics in Dynamic Proxy). I figured I would post that email here as well in case others have thoughts on some of the issues I present.

I am going to dump out some of my experiences here, I have already shared some of these with hammett off list but they may help in the design of the next version of dynamic proxy (and definitely bring up discussion points).
 
The goal of truly supporting generics is the ability to reuse the generic proxy. This goal is not easily realized, I am beginning to question whether or not it is even worthwhile to create generic proxies.
 
Interceptors:
 
In order to have a functional generic dynamic proxy system I need to support generic aware point cuts.
 
Foo<T>.SomeMethod .. applies to all proxy instances
Foo<SomeClass>.SomeMethod .. only applies to proxy instances where T=SomeClass
Foo<T>.SomeMethod where T is ISomething .. dynamic application where T implements ISomething
 
This makes generation of generic proxies nasty at best. If we want to build a reusable proxy we have to build a superset of all defined behavior for any derived versions then conditionally not do anything at those interception points. We can move this behavior out to our interceptor cache ( i.e. simply pass a better context and return null representing no action to be taken) but this is still placing code into our proxies that we know for a fact will never be used.
 
ex:
 
an after interceptor defined only on Foo<int> must be placed on Foo<T> and checked in an if for all other classes .. This would allow us to reuse the generic proxy but has a trade off of performance for the other proxies.
 
This problem becomes compounded when dealing with mixins as someone could define a mixin only to apply to Foo<SomeClass> and not to Foo<T>. As such our previous solution of managing this in an interceptor cache becomes invalid so we are forced to create separate proxies for closed types in many cases. This will alleviate the problem of having garbage interceptor code but now we are also losing the ability to reuse our generic proxy.
 
This also adds a level of complexity to the cache. When given a Foo<SomeClass> you would first look in the cache for a Foo<SomeClass> .. if Foo<SomeClass> did not exist you would then have to analyze the metadata defining any aspects for Foo<SomeClass> to determine if you could use Foo<T> instead or whether you needed to generate a specific Foo<SomeClass> proxy. Providing we only ever _ADD_ behavior to a proxy we could reuse the open type proxies by inheriting from them for the more specific proxy having the inherited proxy adding further functionality to the base proxy ... This becomes interesting as for interceptors it may or may not add interception points meaning we have to inspect heavily the metadata in order to determine whether or not we actually need to create a subclass or whether we are simply receiving different interceptors at the same locations (easy operation but kind of annoying)
 
Of course to do things right you would want an operation that could also REMOVE an interception, example I want to add an interceptor to add on all List<T> except for List<MyUseVeryOftenClass> ... this operation obviously makes inheritance a bit more tricky.
 
Another issue I have come across in dealing with generic mixins is the following situation.
 
public class A<T,V> {}
public interface B<T,V>{}
public class Bimplementor<T,V> {}
I want to mixin B with A though BImplementor .. when I go to generate my proxy there are two related issues.
 
1) Are T,V pointing to the same thing? :)
2) If not what should B's T,V be... I need some way of being given this metadata
 
they have defined .. (in some fictitious language that I will use through out this)
Class A<T,V> mixin B, BImplementor<A, B>
 
My proxy would need to be defined something similar to the following ..
 
public class AProxy <T,V,A,B> : B<A,B> {
}
 
because the T,V does not match up .. when I go to create an instance of this proxy I need to know what to put into A and B as they will not be provided. One could quite easily force a closed definition in the aspect definition i.e.
 
Class A<T,V> mixin B, BImplementor<int, double>
 
which would help many of these issues
 
The flip side of this is if we want them to match up (i.e. we want to reuse the same parameters of the original class)
 
public class AProxy<T,V> : B<T,V> {
}
 
perhaps an aspect definition similar to
 
class A<T,V> mixin B, BImplementor<T,V>
 
But there should also be a fair amount of error handling to insure that all values of T and V are in fact valid for A and B of the related interface
 
I guess the real point I am trying to make is that there are all sorts of fun conditions where we end up just using a closed proxy anyways .. How often will we really get to use an open proxy, are the times that we can use them worth all of the complexity? Similar behaviors could have been had in 1.x by allowing inheritance within definitions (and inheriting proxies) but I have yet to see an implementation that did this .. ex:
 
Class A mixin B, BImplementor
 
applies not only to A but all classes that inherit from A
 
 
 
In my particular case I have even further problems because I support multiple non-pure base class aggregation with a pattern similar to this http://www.codeproject.com/csharp/smip.asp . The additional problem here is that while A<T> and B<T> may have no public fields (I therefor inherit from A<T>) .. I may run into a point where B<T> ends up having a public field later on (as such I would need to inherit from B<T> and aggregate A<T> in order to support the public fields)
 
Just some food for thought :)
 
Cheers,
 
Greg


posted @ Monday, May 29, 2006 1:02 PM | Feedback (2)

 

 

Copyright © Greg Young