Performance

[kzaher]

First of all, great job guys, just great. I'm blown away. I have just a tiny comment.

I downloaded the source code and noticed this line of code

• (NSUInteger)wordsBackward:(NSUInteger)index count:(NSUInteger)count option:(MOTION_OPTION)opt{ ASSERT_VALID_RANGE_WITH_EOF(index); if( 1 >= index) return 0;

  NSUInteger pos = index-1;

  unichar lastChar= [[self string] characterAtIndex:pos]; // < --- this is the line

Are you reading the whole string from the window every time you are doing some search. That could be an issue with long source files. Maybe there exists a smarter way of getting the string content from the view.

Anyway, great job guys.

[kzaher]

For example, when i hold { key and want to navigate fast backward, my processor goes to 100% (Intel i7), because of constantly copying of the whole buffer and searching through it, and I don't have such a large file.

[JugglerShu]

I was also wondering if such code has any problem with perfromance. I'm really newbie to Objective-C and cocoa and if you know about how they are working can you let me know what's happening on the method call?

What I think is following

• [self string] is a method which retturns pointer to NSString and this is just a copy of 8 byte pointer (which I think not really big problem)
• [[self string] characterAtIndex:pos] is O(1) access if the NSString internal expression is just an array

So... I'm still not really know which pert is really the problem... Is there any string copying inside NSString methods?

[kzaher]

1rst I'll tell you how to reproduce the problem. Open Activity monitor (so you can monitor CPU). Open XCode that has your plugin configured. Open XVim project source code. Open some file (for example Evaluators/XVimMotionEvaluator.m). Put cursor to the top of the file and hold w. Watch Activity Monitor and you will see how processor is at 100% (do not be fulled if you have 8 cores like I and activity monitor says it's 12,5% or something like that :), that means that one core is at 100%, and because work can't be parallelized, it shows only about 12,5% ).

I'm sorry if this detailed presentation offended you, but I needed to be sure that what i'm talking about is right. Please try to reproduce the problem on your system.

Now, let me explain why I believe what you think is impossible.

• • [[self string] characterAtIndex:pos] is O(1) access if the NSString internal expression is just an array I belive that is true.
• • [self string] is a method which returns pointer to NSString and this is just a copy of 8 byte pointer (which I think not really big problem)

Well, I think that is impossible. That would mean that you get direct access to the internal storage buffer of the window. If that was the case, when you typed something to the window, that change would be directly propagated to the fetched string reference. That is a bad design smell.

Also, if that was the case, you would get a reference to the instance of NSMutableString. And that would also mean that if you added something to the string, the change would be propagated to to internal storage of the window. That is also a bad design decision.

So I belive that every time you request access to string property, you invoke information collecting engine, that copies the content of the formatted text to requested string.

If you want, I can try to help you addressing these performance issues because i think your project is so fck great and i've been googling so long to find something like this.

[kzaher]

Ok, i believe i have found a method that can help you

[[[view textStorage] attributedSubstringFromRange: NSMakeRange(..., ...)] string]

first get attributed substring, and then convert it to string.

Some kind of optimized search would be needed, but can make a great difference in performance.

[kzaher]

Also for length of text

instead of

• (BOOL) isEOF:(NSUInteger)index{ ASSERT_VALID_RANGE_WITH_EOF(index);

  return [[self string] length] == index; }

you can use

• (BOOL) isEOF:(NSUInteger)index{ ASSERT_VALID_RANGE_WITH_EOF(index);

  return [[self textStorage] length] == index; }

[JugglerShu]

I never feel you offend me. I really want your help. I confirmed the cpu power thing.

Since I'm really new to XCode and Obj-C it takes time to fix one problem. If you already know the exact problem I really want to know it and fix it by the information. (Sorry I should do it by myself but the time I can use on this project is limited...)

I'll try fix it with your hints.

Thanks a lot.

[JugglerShu]

And just as note why I thought [view string] is copy of a pointer is because of the following web site and my experience.

http://vivacocoa.jp/objective-c3e/chapter6c.html ( This is japanese site)

What you can see this page is

 [[textView string] copy]

This looks that [view string] is just an copy of a pointer. And the site also refers that the string returned by [view string] may be changed after obtaining the pointer.

So this means the following is TRUE...

"If that was the case, when you typed something to the window, that change would be directly propagated to the fetched string reference. "

Anyway I still need some time to investigate the problem. Wait for a while patiently.

Thanks

[kzaher]

I've just implemented fixes for me, and I would like to share them with the community. Use these methods in NSTextView+VimMotion.m

-(NSUInteger)length { return [[self textStorage] length]; }

-(BOOL)characterAtIndex:(NSUInteger)index { return [[[self attributedSubstringFromRange:NSMakeRange(index, index + 1)] string] characterAtIndex:0]; }

-(NSString*)substringAtRange:(NSRange)range { return [[self attributedSubstringFromRange:range] string]; }

to efficiently perform these operations. I've implemented these fixes in my local source code and performance improvement is drastic.

I know they are not perfect, and further optimizations could be made, but my CPU doesn't sweat anymore :)

If you like, I can implement it for you, just make me a contributor or something so that I can make those changes. This project is a life saver.

[tomlu]

You do not need to be a contributor. Just fork the project from github, push your changes to your fork and submit a pull request. Your changes will be reviewed and merged into the mainline.

Help like this is always appreciated, thanks very much.

[kzaher]

This is totally weird, and I don't understand what is happening. NSString is IMMUTABLE how can this be happening, can someone please explain it to me, because I sure can not.

Change the code to this.

// #import <objc/runtime.h> // NSString _lastString = nil; //- (NSUInteger)wordsForward:(NSUInteger)index count:(NSUInteger)count option:(MOTIONOPTION)opt info:(XVimWordInfo)info{ // ASSERT_VALID_RANGE_WITH_EOF(index); // NSAssert(nil != info, @"Specify info");

// NSString *currentString = [self string]; // if (lastString != nil) // NSLog(@"Last string is %s: %@", class_getName([lastString class]), lastString); // NSLog(@"Current string is %s: %@", class_getName([currentString class]), currentString); // [lastString release]; // lastString = [currentString retain];

// NSInteger pos = index; // info->isFirstWordInALine = NO; // info->lastEndOfLine = NSNotFound; // info->lastEndOfWord = NSNotFound;

......

Deploy code, open console and watch the print.

Go to the start of some file in XCode and press w Now enter I 'wtf'. Now escape and w again. From the console print it looks like changes really are propagated to the string object that we fetched on the last w press.

HOW CAN THAT BE, TYPE IS NSCFString (NSString) and that type is immutable https://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSString_Class/Reference/NSString.html

Now I don't understand anything anymore.

[tomlu]

The NSString might be an NSMutableString. You can't mutate the string through your reference, but someone else might be.

Also, I've perused the docs for NSTextStorage. It appears the string method returns the underlying representation directly. There should therefore not be any performance problems with the current approach. However, I can corroborate that Xcode is tying up an entire core as soon as you use it, so there's definitely something to what you are saying. I look forward to analysing the issue further once you submit your pull request.

[JugglerShu]

This is just my guess but the problem could be "characterAtIndex" method. Since its internal object is "MUTTABLE" the NSString object we operate on may not be just an array of characters. If its internal structure is an array "insert" or "delete" characters may take a lot of copying and that is not likely to be implemented as NSMutableString. Maybe some kind of linked list or some other structure they use. And if its true characterAtIndex takes O(n)...

Sorry that I do not have much time to do an experiment on this...

[tomlu]

I've profiled XVim and I can't really see anything major. The key handling is pretty fast even when hammering keys. I'm certainly not seeing any string functions consuming any noticeable CPU time.

I thought rendering may be slow (XVim instructs a redundant redraw of the window even though just the block cursor changes), but fixing this didn't help.

My final thought is that perhaps XVim is generating a lot of garbage which puts pressure on the GC. I haven't looked into this.

[kzaher]

I've spent a few days debugging this issue and I believe that the problem is in XCode and not your code. If you don't use XVIM and move word by word using the arrows, the same issue occurs. Incredible, but it nails one core on my CPU to 100%.

Why it manifested here, well, VI commands enable natural fast movement between words, so apple testers probably missed that.

Anyway, since I've spent the last few days, this is what i've found out, so maybe it helps someone.

• [self string] is a method which retturns pointer to NSString and this is just a copy of 8 byte pointer - TRUE
• [[self string] characterAtIndex:pos] is O(1) access if the NSString internal expression is just an array - TRUE

NSString returned is NSCFString NSMutableString has also a private class named NSCFString You can source code for CFString here http://opensource.apple.com/source/CF/CF-635.19/.

Looks like __NSCFString is internal storage for editor.

NSMutableString (__NSCFString) behaves like vector in C++ or List in C#. 2x storage allocation strategy, array for storage, O(1) access for characterAtIndex. Building string by adding to the front O(n^2) because of copying, to the end O(n).

[tomlu]

Ok, thanks for your investigation.

[JugglerShu]

These are really good information. I learned a lot from this. Thanks.