macOS Help with NSArray and C array

[Richard Birkett]

That is my partially commented code for finding primes, I used to collect them in an NSMutableArray but doing it in C halved the time. My problem is that I need to create an NSArray to play with once it has finished calculations but it keeps throwing errors as I detailed in the last few lines. help appreciated

- (IBAction)customStart:(id)sender {
	NSArray *result = [self runPrimesFromStart:8 toFinish:1000000];
}

- (NSArray *)runPrimesFromStart:(unsigned long long)startValue toFinish:(unsigned long long)endValue
{
	NSLog(@"start");
		//NSMutableArray *primeNumbers = [NSMutableArray array];
	
		//if startValue is even then use the next odd instead
	unsigned long long start = startValue%2 == 0 ? ++startValue : startValue;
		//if endValue is even then make the if look for values below, if odd include it, note the n<end below
	unsigned long long end = endValue%2 == 0 ? endValue : ++endValue ;
		//make array half the range since it will not all be needed
	unsigned long long primeNumbers[((2+end-start)/2)];
	unsigned long long primeCount = 0;
	for (unsigned long long n = startValue; n<end; (n++, n++)) {
		BOOL y = YES;
		for (unsigned long long x = 3; (x <= sqrtl(n)) && y; x++) {
				//NSLog(@"in repeat");
			if (n%x == 0) {
				y = NO;
					//NSLog(@"%llu is not prime", n);
			}
		}
		if (y == YES) {
			++primeCount;
			primeNumbers[primeCount] = n;
				//[primeNumbers addObject:[NSNumber numberWithUnsignedLongLong: n]];
				//NSLog(@"%llu is prime", n);
		}
			//NSLog(@"finished checking");
	}
		//make primeCount the first item of the array
	primeNumbers[0] = primeCount;
//logging item 0, 1 and 2 is successful here
	NSArray *result = [NSArray arrayWithObjects:primeNumbers count:primeCount];//throws "Program received signal 'EXC_BAD_ACCESS' "
	return result;
}

And if you like it would be really nice if you looked at https://forums.macrumors.com/threads/1216402/



Richard

 

[kainjow]

NSArray can only hold objects, but primeNumbers is a C array. You need to either wrap those values in an NSNumber or use CFArray which doesn't require objects.

 

[Kranchammer]

Your problem is probably here:

primeNumbers[0] = primeCount;
//logging item 0, 1 and 2 is successful here
	NSArray *result = [NSArray arrayWithObjects:primeNumbers count:primeCount];//throws "Program received signal 'EXC_BAD_ACCESS' "
	return result;

primeNumbers is a long long pointer, not an a NIL terminated list of objects the method needs.

 

[foidulus]

Just an FYI, your NSMutableArray would have run faster if you had given it a decent capacity when you allocated it(the same capacity as your C array would work). With a mutable array, every time you go over the capacity it has to go allocate more memory and do all sorts of other nasty stuff that takes a lot of time. Allocating a good capacity from the getgo would help avoid a lot of that.

That being said, C arrays are still going to be faster most of the time since they do not have to separate allocations for each object and store the data contiguously in memory which helps increase the cache hit percentage etc. However in your program I doubt the difference would be 2x. You should try it out and let us know.

 

[Richard Birkett]

Thanks for the replies,

Basically with further manual efficiencies NSMutableArray is down to 1 to 1.1 seconds with checking from 9 to 1000000 (better than 36 seconds in AppleScript!!!).

I would like to tell you the c array news but it keeps throwing exception, here's the code ('#if 1' for c array, '0' for NSMutableArray)

- (IBAction)customStart:(id)sender {
		//unsigned long long startFinish[2];
	unsigned long long start = 8;
	unsigned long long end = 1000000;
	NSArray *startFinish =[NSArray arrayWithObjects:[NSNumber numberWithUnsignedLongLong:start], [NSNumber numberWithUnsignedLongLong:end], nil];
	[NSThread detachNewThreadSelector:@selector(runPrimesWithStartAndEnd:) toTarget:self withObject:startFinish];
	 //NSMutableArray *result = [self runPrimesWithStartAndEnd:startFinish];
		//NSArray *result = [self runPrimesFromStart:8 toFinish:1000000];
		//unsigned long long example = result[1];
	 //NSLog(@"%@",result);
}

- (void)hello:(NSMutableArray *)result
{
		//compare performance of main thread vs. detached
	NSLog(@"%@", result);
}

#if 1
- (NSMutableArray *)runPrimesWithStartAndEnd:(NSArray *)startEnd
{
	NSLog(@"C array start in main thread?: %i", [NSThread isMainThread]);
		//NSMutableArray *primeNumbers = [NSMutableArray array];
	
		//if startValue is even then use the next odd instead
	unsigned long long start = [[startEnd objectAtIndex:0] unsignedLongLongValue];
	if (start%2 == 0) ++start;
		//if endValue is even then make the if look for values below, if odd include it, note the n<end below
	unsigned long long end = [[startEnd objectAtIndex:1] unsignedLongLongValue];
	if (end%2 == 1) ++end;
		//make array half the range since it will not all be needed
	NSLog(@"primeNumbers size: %llu", ((2+end-start)/2));// returns a correct value
	unsigned long long primeNumbers[((2+end-start)/2)]; //any NSLog after this line throws exc bad access, if there are no logs it throws one like the picture at the bottom
	NSLog(@"1");// like here
	unsigned long long primeCount = 0;
	NSLog(@"2");//here
	for (unsigned long long n = start; n<end; (n++, n++)) {
		NSLog(@"3");//here
		BOOL y = YES;
		NSLog(@"in repeat 1");//here
		for (unsigned long long x = 3; (x <= sqrtl(n)) && y; x++) {
				NSLog(@"in repeat 2");//here
			if (n%x == 0) {
				y = NO;
					//NSLog(@"%llu is not prime", n);
			}
		}
		if (y == YES) {
			++primeCount;
			primeNumbers[primeCount] = n;
				//[primeNumbers addObject:[NSNumber numberWithUnsignedLongLong: n]];
				//NSLog(@"%llu is prime", n);
		}
			//NSLog(@"finished checking");
	}
		//make primeCount the first item of the array therefore making the count +1
	primeNumbers[0] = primeCount;
	NSLog(@"C array end");
	NSMutableArray *result = [NSMutableArray array];
	for (unsigned long long repeatCount = 0; repeatCount<=primeCount; repeatCount++) {
		[result addObject:[NSNumber numberWithUnsignedLongLong: primeNumbers[repeatCount]]];
	}
	
	return result;
}
#else //works perfectly
- (NSMutableArray *)runPrimesWithStartAndEnd:(NSArray *)startEnd
{
	NSLog(@"NSMutableArray start in main thread?: %i", [NSThread isMainThread]);
	NSMutableArray *primeNumbers = [NSMutableArray array];
	
		//if startValue is even then use the next odd instead
	unsigned long long start = [[startEnd objectAtIndex:0] unsignedLongLongValue];
	if (start%2 == 0) ++start;
		//if endValue is even then make the if look for values below, if odd include it, note the n<end below
	unsigned long long end = [[startEnd objectAtIndex:1] unsignedLongLongValue];
	if (end%2 == 1) ++end;
	for (unsigned long long n = start; n<end; (n++, n++)) {
		BOOL y = YES;
		for (unsigned long long x = 3; (x <= sqrtl(n)) && y; x++) {
			if (n%x == 0) {
				y = NO;
			}
		}
		if (y == YES) {
				[primeNumbers addObject:[NSNumber numberWithUnsignedLongLong: n]];
		}
	}
	NSLog(@"NSMutableArray end");
	[self performSelectorOnMainThread:@selector(hello:) withObject:primeNumbers waitUntilDone:NO];
	return primeNumbers;
}
#endif

 

[Richard Birkett]

Very weird, changed code to the following and it worked, but without the final perform... here it either throws on main or 'primeNumber[primeCount] = n':

- (NSMutableArray *)runPrimesWithStartAndEnd:(NSArray *)startEnd
{
	NSLog(@"C array start in main thread?: %i", [NSThread isMainThread]);
		//NSMutableArray *primeNumbers = [NSMutableArray array];
	
		//if startValue is even then use the next odd instead
	unsigned long long start = [[startEnd objectAtIndex:0] unsignedLongLongValue];
	if (start%2 == 0) ++start;
		//if endValue is even then make the if look for values below, if odd include it, note the n<end below
	unsigned long long end = [[startEnd objectAtIndex:1] unsignedLongLongValue];
	if (end%2 == 1) ++end;
		//make array half the range since it will not all be needed
	NSLog(@"primeNumbers size: %llu", ((2+end-start)/2));
	unsigned long long primeNumbers[((2+end-start)/2)];
	unsigned long long primeCount = 0;
	for (unsigned long long n = start; n<end; (n++, n++)) {
		BOOL y = YES;
		for (unsigned long long x = 3; (x <= sqrtl(n)) && y; x++) {
			if (n%x == 0) {
				y = NO;
					//NSLog(@"%llu is not prime", n);
			}
		}
		if (y == YES) {
			++primeCount;
			primeNumbers[primeCount] = n;
				//NSLog(@"%llu is prime", n);
		}
			//NSLog(@"finished checking");
	}
		//make primeCount the first item of the array therefore making the count +1
	primeNumbers[0] = primeCount;
	NSLog(@"C array end");
	NSMutableArray *result = [NSMutableArray array];
	for (unsigned long long repeatCount = 0; repeatCount<=primeCount; repeatCount++) {
		[result addObject:[NSNumber numberWithUnsignedLongLong: primeNumbers[repeatCount]]];
	}
	[self performSelectorOnMainThread:@selector(hello:) withObject:result waitUntilDone:NO];
	return result;
}

Drum roll...

Over a check of ten million they both take variably around 26 seconds, it is so random one beats the other who gets revenge the next time, it is ridiculous, although I would say the C array way was generally faster by .1 but thats too small to care about. I will do further tests and look at memory and cpu usage to decide which to stick with, obviously reliability is a major factor but I want to know why it is behaving like this for the C array, it has no obvious reason to...

 

[Sydde]

Are you using 78 Mb of stack space for your C array? (That would be how much space ten million 64 bit integers would consume — the main thread stack in 8 Mb.)

 

[Richard Birkett]

Are you using 78 Mb of stack space for your C array? (That would be how much space ten million 64 bit integers would consume — the main thread stack in 8 Mb.)

I don't know what either a stack or stack space is, and yes I am allocating arrays that large.

 

[Sydde]

I don't know what either a stack or stack space is, and yes I am allocating arrays that large.

This statement in your code

unsigned long long primeNumbers[((2+end-start)/2)];

creates your large array as an "automatic" variable. Automatic variables live in a specific region of memory called "the stack". The stack is used for transient values such as subroutine or method parameters, these automatic variables, and for keeping track of program flow (when a subroutine or method exits back to its caller/sender, a vector is pulled so that execution can resume where it left off).

When you declare a variable in code, space on the stack is set aside for it (we might say the top of the stack is raised to make room for it). The OS sets up a stack for each thread of a program. The main thread is given 8 Mb, IIRC, and any other threads get half a meg. If you raise the top of the stack beyond its ceiling, you program will start to access memory somewhere else than is should be doing. Luckily, memory management can often detect stack overruns and throw an exception, but sometimes not and rather ugly crashes can occur.

If you really need to use that much memory, you should allocate it on the heap. One way to do that is to allocate a block with malloc(), which you would later need to dispose of with free(). Another possibility would be to allocate it as a NSMutableData object and use the -mutableBytes method to assign your C array pointer. The advantage to the latter is that you can use a convenience method like

NSMutableData *arrayHolder = [NSMutableData dataWithCapacity:( 2 + end - start ) / 2];

so that your code will not have to worry about freeing up memory when you are done with it.

I think I would do it like this:

{
    // ...

    NSMutableData *arrayHolder = [[NSMutableData alloc] init]; // empty data object

    UInt64 *primeNumbers; // this is the same as unsigned long long in 10.5 +

    // ... calculate data block size ...

    [arrayHolder setLength:( 2 + end - start ) / 2]; // data block will be filled with zeros
    primeNumbers = [arrayHolder mutableBytes];

    // ... do your calculations and stuff — code will be unchanged because the array syntax can be used as is on a pointer ...

    [arrayHolder release]; // ... free up the block of memory when you are done with it
}

 

[Richard Birkett]

Thank you very much, worked well.

 

[chown33]

{
    // ...

    NSMutableData *arrayHolder = [[NSMutableData alloc] init]; // empty data object

    UInt64 *primeNumbers; // this is the same as unsigned long long in 10.5 +

    // ... calculate data block size ...

    [COLOR="Red"][arrayHolder setLength:( 2 + end - start ) / 2][/COLOR]; // data block will be filled with zeros
    primeNumbers = [arrayHolder mutableBytes];

    // ... do your calculations and stuff — code will be unchanged because the array syntax can be used as is on a pointer ...

    [arrayHolder release]; // ... free up the block of memory when you are done with it
}

I've red-hilited a bug.

setLength: sets the length of the NSMutableData to that number of bytes. The original array declaration:

unsigned long long primeNumbers[((2+end-start)/2)];

is for that number of unsigned long long's. The latter is 8 bytes each.

The only reason it works is because the frequency of primes is staying below 1/8 for the test. For certain ranges, the frequency of primes exceeds 1/8, and you'll overrun memory with possibly grave consequences.


It's not clear what the purpose of this function is. What is the reason the list of primes is needed? Or is this just some kind of speed benchmark?

It might be faster (and would take less memory) to use a prime sieve. Even the sieve of Eratosthenes, with one byte per flag, would use less memory. E.g. for a range of 1000 (i.e. end-start = 1000), (2+end-start)/2 will be 501 8-byte numbers, or 501*8 = 4008 bytes. The same range in a sieve of Eratosthenes would take 1000 bytes using the simplest implementation.

 

[Richard Birkett]

I did pick up that 'bug' and fix accordingly, although now I'm back to the NSMutableArray for ease and feedback. I am doing this to try and develop my basic knowledge of C and it has helped a lot, plus I'm a mathematician at heart, I also AppleScript a lot and always wanted to know how efficient it is... the same algorithm is 60 times slower!

 

[gnasher729]

Just wondering: Why is a variable named "y" and not for example "isprime"? And why do you continue dividing by more numbers once you found that a number can be divided by say 3 or 5?

 

[Richard Birkett]

Because I am trying to relate it visually to an AppleScript which stupidly used the same scheme.

I don't, notice the && y, I have logged it to prove it only check odd numbers until there is a factor.

for (unsigned long long x = 3; (x <= sqrtl(n)) && y; x++) {
	if (n%x == 0) {
		y = NO;
			//NSLog(@"%llu is not prime", n);
	}
}