It is currently Thu Mar 28, 2024 4:59 pm

Mulle kybernetiK Optimization

Forum for Optimizations around Cocoa and Mac OS X

Specialized NSMutableArray subclass for NSRanges?

Your code runs too slow. In need of a clue ? Ask your questions here.

Moderator: Nat!

User avatar
 
Posts: 2
Joined: Fri Aug 06, 2004 1:07 am
Website: http://www.mulle-kybernetik.com/~znek/

Specialized NSMutableArray subclass for NSRanges?

Post by znek » Mon Sep 06, 2004 1:29 pm

Hi there,

my current pet project - an editor for SOPE templates (think of a specialized HTML editor) needs to deal with arrays of ranges for a variety of reasons (finding tags quickly, associating character locations with line numbers, etc.). Currently I'm doing this encapsulating NSRange structs into objects (by means of EDRange). I'm happy with the results that gives me, especially I can sort these ranges using various comparisons (by location, by length) to speed up certain use cases. However some DOUBT remains whether this is the most efficient thing to do it ... I don't really know how much hassle it would be to implement a subclass of NSMutableArray that operates on structs (NSRange) rather than on objects? Probably the best thing would be to have something like this defined generically (probably with some macros). Or should I go with ObjC++ and use STL for this (I don't really have a clue about STL, so probably this idea is plain sick ;-)?

Someone please wise me up. Cheers!
too slow is a good reason to upgrade!

User avatar
 
Posts: 42
Joined: Fri Aug 06, 2004 9:20 am
Location: Bochum
Website: http://www.mulle-kybernetik.com/weblog

Post by Nat! » Mon Sep 06, 2004 4:44 pm

I don't think it would be good to make this a NSMutableArray subclass. Techically it isn't really possible, as you can't call retain on NSRange and neither is NSRange an id so you would get lots of casting pressure for that hack.

description on that subclass would also fail pretty badly.

 
Posts: 5
Joined: Tue Sep 07, 2004 4:50 am

Post by whitenoise » Tue Sep 07, 2004 5:00 am

STL is not generally going to help you with optimization if your algorithms are already sane. It is likely to make things much, much worse by adding to your VM working set.

User avatar
 
Posts: 42
Joined: Fri Aug 06, 2004 9:20 am
Location: Bochum
Website: http://www.mulle-kybernetik.com/weblog

Post by Nat! » Tue Sep 07, 2004 9:53 pm

Here is a rudimentary implementation of an array that contains NSRanges, I think it works, but haven't tested it much. (Maybe a I should try Mock Objects :wink:)

The immutable class.

Code: Select all

#import <Foundation/Foundation.h>


@interface MulleNSRangeArray : NSObject
{
   NSRange        *array_;
   unsigned int   count_;
}

- (id) initWithRanges:(NSRange *) ranges
                count:(unsigned int) count;

- (unsigned int) count;
- (NSRange) rangeAtIndex:(unsigned int) index;

@end




Code: Select all

#import "MulleNSRangeArray.h"


@implementation MulleNSRangeArray

- (id) initWithRanges:(NSRange *) ranges
                count:(unsigned int) count
{
   size_t    len;
   
   [super init];
   
   len    = sizeof( NSRange) * count;
   array_ = malloc( len);
   memcpy( array_, ranges, len);
   count_ = count;
   
   return( self);
}


- (void) dealloc
{
   free( array_);
   
   [super dealloc];
}


- (unsigned int) count
{
   return( count_);
}


- (NSRange) rangeAtIndex:(unsigned int) index
{
   NSParameterAssert( index < count_);
   
   return( array_[ index]);
}


@end



and the mutable subclass

Code: Select all

#import "MulleNSRangeArray.h"


@interface MulleMutableNSRangeArray : MulleNSRangeArray
{
   unsigned int   capacity_;
}


- (void) addRange:(NSRange) range;
- (void) removeRangeAtIndex:(unsigned int) index;


@end


Code: Select all

#import "MulleMutableNSRangeArray.h"


@implementation MulleMutableNSRangeArray


#define MIN_CAPACITY   4


- (id) initWithRanges:(NSRange *) ranges
                count:(unsigned int) count
{
   [super initWithRanges:ranges
                   count:count];
   capacity_ = count_;
   
   return( self);
}


- (void) addRange:(NSRange) range
{
   if( capacity_ == count_)
   {
      capacity_ <<= 1;
      if( capacity_ < MIN_CAPACITY)
         capacity_ = MIN_CAPACITY;
   
      array_ = realloc( array_, sizeof( NSRange) * capacity_);
   }     
   array_[ count_++] = range;
   return;
}
   
   
- (void) removeRangeAtIndex:(unsigned int) index
{
   NSParameterAssert( index <= count_);
   
   --count_;
   if( index < count_)
      memcpy( &array_[ index], &array_[ index + 1], sizeof( NSRange) * (count_ - index));
}



@end


And sadly, totally unoptimized :P


Return to “Requests - Questions - Help”

Who is online

Users browsing this forum: No registered users and 0 guests