Showing posts with label Cocoa. Show all posts
Showing posts with label Cocoa. Show all posts

Tuesday, August 9, 2022

Native-GUI distributed system in a tweet

If I've been a bit quiet recently it's not due to lack of progress, but rather the very opposite: so much progress in Objective-S land hat my head is spinning and I am having a hard time both processing it all and seeing where it goes.

But sometimes you need to pause, reflect, and show your work, in whatever intermediate state it currently is. So without further ado, here is the distributed system, with GUI, in a tweet:

It pops up a window with a text field, and stores whatever the user enters in an S3 bucket. It continues to do this until the user closes the window, at which point the program exits.

Of course, it's not much of a distributed system, particularly because it doesn't actually include the code for the S3 simulator.

Anyway, despite fitting in a tweet, the Objective-S script is actually not code golf, although it may appear as such to someone not familiar with Objective-S.

Instead, it is a straightforward definition and composition of the elements required:

  1. A storage combinator for interacting with data in S3.
  2. A text field inside a window, defined as object literals.
  3. A connection between the text field and a specific S3 bucket.
That's it, and it is no coincidence that the structure of the system maps directly onto the structure of the code. Let's look at the parts in detail.

S3 via Storage Combinator

The first line of the script sets up an S3 scheme handler so we can interact with the S3 buckets almost as if they were local variables. For example the following assignment statement stores the text 'Hello World!' in the "msg.txt" file of "bucket1":

   s3:bucket1/msg.txt ← 'Hello World!'
Retrieving it works similarly:

   stdout println: s3:bucket1/msg.txt
The URL of our S3 simulator is http://defiant.local:2345/, so running on host defiant in the local network, addressed by Bonjour and listening on port 2345. As Objective-S supports Polymorphic Identifiers (pdf), this URL is a directly evaluable identifier in the language. Alas, that directness poses a problem, because writing down an identifier in most programming languages yields the value of the variable the identifier identifies, and Objective-S is no exception. In the case of http://defiant.local:2345/, that value is the directory listing of the root of the S3 server, encoded as the following XML response:

<?xml version="1.0" encoding="UTF-8"?>
<ListAllMyBucketsResult xmlns="http://s3.amazonaws.com/doc/2006-03-01/">
<Owner><ID>123</ID><DisplayName>FakeS3</DisplayName></Owner>
<Buckets>
<Bucket>
<Name>bucket1</Name>
<CreationDate>2022-08-10T15:18:32.000Z</CreationDate>
</Bucket>
</Buckets>
</ListAllMyBucketsResult>
That's not really what we want, we want to refer to the URL itself. The ref: allows us to do this by preventing evaluation and thus returning the reference itself, very similar to the & operator that creates pointers in C.

Except that an Objective-S reference (or more precisely, a binding) is much richer than a C pointer. One of its many capabilities is that it can be turned into a store by sending it the -asScheme message. This new store uses the reference it was created from as its base URL, all the references it receives are evaluated relative to this base reference.

The upshot is that with the s3: scheme handler defined and installed as described, the expression s3:bucket1/msg.txt evaluates to http://defiant.local:2345/bucket1/msg.txt.

This way of defining shorthands has proven extremely useful for making complex references usable and modular, and is an extremely common pattern in Objective-S code.

Declarative GUI with object literals

Next, we need to define the GUI: a window with a text field. With object literals, this is pretty trivial. Object literals are similar to dictionary literals, except that you get to define the class of the instance defined by the key/value pairs, instead of it always being a dictionary.

For example, the following literal defines a text field with certain dimensions and assigns it to the text local variable:

   text ← #NSTextField{ #stringValue:'',#frame:(10@45 extent:180@24) }.
And a window that contains the text field we just defined:
   window ← #NSWindow{ #frame:(300@300 extent:200@105),#title:'S3', #views:#[text]}.
It would have been nice to define the text field inline in its window definition, but we currently still need a variable so we can connect the text field (see next section).

Connecting components

Now that we have a text field (in a window) and somewhere to store the data, we need to connect these two components. Typically, this would involve defining some procedure(s), callback(s) or some extra-linguistics mechanism to mediate or define that connection. In Objective-S, we just connect the components:

   text → ref:s3:bucket1/msg.txt.
That's it.

The right-arrow "→" is a polymorphic connection "operator". The complete connection is actually significantly more complex:

  1. From a port of the source component
  2. To a role of the mediating connector compatible with that source port
  3. To a role of the mediating connector compatible with the target object's port
  4. To that compatible port of the target component
If you want, you can actually specify all these intermediate steps, but most of the time you don't have to, as the machinery can figure out what ports and roles are compatible. In this case, even the actual connector was determined automatically.

If we didn't want a remote S3 bucket, we could also have stored the data in a local file, for example:

   text → ref:file:/tmp/msg.txt.
That treats the file like a variable, replacing the entire contents of the file with the text that was entered. Speaking of variables, we could of course also store the text in a local variable:

   text → ref:var:message.
In our simple example that doesn't make a lot of sense because the variable isn't visible anywhere and will disappear once the script terminates, but in a larger application it could then trigger further processing.

Alternatively, we could also append the individual messages to a stream, for example to stdout:

   text → stdout.
So every time the user hits return in the text field, the content of the text field is written to the console. Or appended to a file, by connecting to the stream associated with the file rather the file reference itself:
   text → ref:file:/tmp/msg.txt outputStream.
This doesn't have to be a single stream sink, it can be a complex processing pipeline.

I hope this makes it clear, or at least strongly hints, that this is not the usual low-code/no-code trick of achieving compact code by creating super-specialised components and mechanisms that work well for a specific application, but immediately break down when pushed beyond the demo.

What it is instead is a new way of creating components, defining their interfaces and then gluing them together in a very straightforward fashion.

Eval/apply vs. connect and run

Having constructed our system by configuring and connecting components, what's left is running it. CLIApp is a subclass of NSApplication that knows how to run without an associated app wrapper or Info.plist file. It is actually instantiated by the stui script runner before the script is started, with the instance dropped into the app variable for the script.

This is where we leave our brave new world of connected components and return (or connect with) the call/return world, similar to the way Cocoa's auto-generated main with call to NSApplicationMain() works.

The difference between eval/apply (call/return) and connect/run is actually quite profound, but more on that in another post.

Of course, we didn't leave call/return behind, it is still present and useful for certain tasks, such as transforming an element into something slightly different. However, for constructing systems, having components that can be defined, configured and connected directly ("declaratively") is far superior to doing so procedurally, even than the fluent APIs that have recently popped up and that have been mislabeled as "declarative".

This project is turning out even better than I expected. I am stoked.

Monday, June 20, 2022

Blackbird: A reference architecture for local-first connected mobile apps

Wow, what a mouthful! Although this architecture has featured in a number of my other writings, I haven't really described it in detail by itself. Which is a shame, because I think it works really well and is quite simple, a case of Sophisticated Simplicity.

Why a reference architecture?

The motivation for creating and now presenting this reference architecture is that the way we build connected mobile apps is broken, and none of the proposed solutions appear to help. How are they broken? They are overly complex, require way too much code, perform poorly and are unreliable.

Very broadly speaking, these problems can be traced to the misuse of procedural abstraction for a problem-space that is broadly state-based, and can be solved by adapting a state-based architectural style such as in-process REST and combining it with well-known styles such as MVC.

More specifically, MVC has been misapplied by combining UI updates with the model updates, a practice that becomes especially egregious with asynchronous call-backs. In addition, data is pushed to the UI, rather than having the UI pull data when and as needed. Asynchronous code is modelled using call/return and call-backs, leading to call-back hell, needless and arduous transformation of any dependent code into asynchronous code (see "what color is your function") that is also much harder to read, discouraging appropriate abstractions.

Backend communication is also an issue, with newer async/await implementations not really being much of an improvement over callback-based ones, and arguably worse in terms of actual readability. (They seem readable, but what actually happens is different  enough that the simplicity is deceptive).

Overview

The overall architecture has four fundamental components:
  1. The model
  2. The UI
  3. The backend
  4. The persistence
The main objective of the architecture is to keep these components in sync with each other, so the whole thing somewhat resembles a control loop architecture: something disturbs the system, for example the user did something in the UI, and the system responds by re-establishing equilibrium.

The model is the central component, it connects/coordinates all the pieces and is also the only one directly connected to more than one piece. In keeping with hexagonal architecture, the model is also supposed to be the only place with significant logic, the remainder of the system should be as minimal, transparent and dumb as possible.

memory-model := persistence.
persistence  |= memory-model.
ui          =|= memory-model. 
backend     =|= memory-model.

Graphically:

Elements

Blackbird depends crucially on a number of architectural elements: first are stores of the in-process REST architectural style. These can be thought of as in-process HTTP servers (without the HTTP, of course) or composable dictionaries. The core store protocol implements the GET, PUT and DELETE verbs as messages.

The role of URLs in REST is taken by Polymorphic Identifiers. These are objects that can reference identify values in the store, but are not direct pointers. For example, they need to be a able to reference objects that aren't there yet.

Polymorphic Identifiers can be application-specific, for example they might consist just of a numeric id,

MVC

For me, the key part of the MVC architectural style is the decoupling of input processing and resultant output processing. That is, under MVC, the view (or a controller) make some change to the model and then processing stops. At some undefined later time (could be synchronous, but does not have to be) the Model informs the UI that it has changed using some kind of notification mechanism.

In Smalltalk MVC, this is a dependents list maintained in the model that interested views register with. All these views are then sent a #changed message when the model has changed. In Cocoa, this can be accomplished using NSNotificationCenter, but really any kind of broadcast mechanism will do.

It is then the views' responsibility to update themselves by interrogating the model.

For views, Cocoa largely automates this: on receipt of the notification, the view just needs invalidate itself, the system then automatically schedules it for redrawing the next time through the event loop.

The reason the decoupling is important to maintain is that the update notification can come for any other reason, including a different user interaction, a backend request completing or even some sort of notification or push event coming in remotely.

With the decoupled M-V update mechanism, all these different kinds of events are handled identically, and thus the UI only ever needs to deal with the local model. The UI is therefore almost entirely decoupled from network communications, we thus have a local-first application that is also largely testable locally.

Blackbird refines the MVC view update mechanism by adding the polymorphic identifier of the modified item in question and placing those PIs in a queue. The queue decouples model and view even more than in the basic MVC model, for example it become fairly trivial to make the queue writable from any thread, but empty only onto the main thread for view updates. In addition, providing update notifications is no longer synchronous, the updater just writes an entry into the queue and can then continue, it doesn't wait for the UI to finish its update.

Decoupling via a queue in this way is almost sufficient for making sure that high-speed model updates don't overwhelm the UI or slow down the model. Both these performance problems are fairly rampant, as an example of the first, the Microsoft Office installer saturates both CPUs on a dual core machine just painting its progress bar, because it massively overdraws.

An example of the second was one of the real performance puzzlers of my career: an installer that was extremely slow, despite both CPU and disk being mostly idle. The problem turned out to be that the developers of that installer not only insisted on displaying every single file name the installer was writing (bad enough), but also flushing the window to screen to make sure the user got a chance to see it (worse). This then interacted with a behavior of Apple's CoreGraphics, which disallows screen flushes at a rate greater than the screen refresh rate, and will simply throttle such requests. You really want to decouple your UI from your model updates and let the UI process updates at its pace.

Having polymorphic identifiers in the queue makes it possible for the UI to catch up on its own terms, and also to remove updates that are no longer relevant, for example discarding duplicate updates of the same element.

The polymorphic identifier can also be used by views in order to determine whether they need to update themselves, by matching against the polymorphic identifier they are currently handling.

Backend communication

Almost every REST backend communication code I have seen in mobile applications has created "convenient" cover methods for every operation of every endpoint accessed by the application, possibly automatically generated.

This ignores the fact that REST only has a few verbs, combined with a great number of identifiers (URLs). In Blackbird, there is a single channel for backend communication: a queue that takes a polymorphic identifier and an http verb. The polymorphic identifier is translated to a URL of the target backend system, the resulting request executed and when the result returns it is placed in the central store using the provided polymorphic identifier.

After the item has been stored, an MVC notification with the polymorphic identifier in question is enqueued as per above.

The queue for backend operations is essentially the same one we described for model-view communication above, for example also with the ability to deduplicate requests correctly so only the final version of an object gets sent if there are multiple updates. The remainder of the processing is performed in pipes-and-filters architectural style using polymorphic write streams.

If the backend needs to communicate with the client, it can send URLs via a socket or other mechanism that tells the client to pull that data via its normal request channels, implementing the same pull-constraint as in the rest of the system.

One aspect of this part of the architecture is that backend requests are reified and explicit, rather than implicitly encoded on the call-stack and its potentially asynchronous continuations. This means it is straightforward for the UI to give the user appropriate feedback for communication failures on the slow or disrupted network connections that are the norm on mobile networks, as well as avoid accidental duplicate requests.

Despite this extra visibility and introspection, the code required to implement backend communications is drastically reduced. Last not least, the code is isolated: network code can operate independently of the UI just as well as the UI can operate independently of the network code.

Persistence

Persistence is handled by stacked stores (storage combinators).

The application is hooked up to the top of the storage stack, the CachingStore, which looks to the application exactly like the DictStore (an in-memory store). If a read request cannot be found in the cache, the data is instead read from disk, converted from JSON by a mapping store.

For testing the rest of the app (rather than the storage stack), it is perfectly fine to just use the in-memory store instead of the disk store, as it has the same interface and behaves the same, except being faster and non-persistent.

Writes use the same asynchronous queues as the rest of the system, with the writer getting the polymorphic identifiers of objects to write and then retrieving the relevant object(s) from the in-memory store before persisting. Since they use the same mechanism, they also benefit from the same uniquing properties, so when the I/O subsystem gets overloaded it will adapt by dropping redundant writes.

Consequences

With the Blackbird reference architecture, we not only replace complex, bulky code with much less and much simpler code, we also get to reuse that same code in all parts of the system while making the pieces of the system highly independent of each other and optimising performance.

In addition, the combination of REST-like stores that can be composed with constraint- and event-based communication patterns makes the architecture highly decoupled. In essence it allows the kind of decoupling we see in well-implemented microservices architectures, but on mobile apps without having to run multiple processes (which is often not allowed).

Saturday, July 24, 2021

Inserting 130M SQLite Rows per Minute...from a Scripting Language

The other week, I stumbled on the post Inserting One Billion Rows in SQLite Under A Minute, which was a funny coincidence, as I was just in the process of giving my own SQLite/Objective-S adapter a bit of tune-up. (The post's title later had "Towards" prepended, because the author wasn't close to hitting that goal).

This SQLite adapater was a spin-off of my earlier article series on optimizing JSON performance, itself triggered by the ludicrously bad performance of Swift Coding at this rather simple and relevant task. To recap: Swift's JSON coder clocked in at about 10MB/s. By using a streaming approach and a bit of tuning, we got that to around 200MB/s.

Since then, I have worked on making Objective-S much more useful for UI work, with the object-literal syntax making defining UIs as convenient as the various "declarative" functional approaches such as React or SwiftUI. Except it is still using the same AppKit or UIKit objects we know and love, and doesn't force us to embrace the silly notion that the UI is a pure function of the model. Oh, and you get live previews that actually work. But more on that later.

So I am slowly inching towards doing a ToDoMVC, a benchmark that feels rather natural to me. While I am still very partial to just dumping JSON files, and the previous article series hopefully showed that this approach is plenty fast enough, I realize that a lot of people prefer a "real" database, especially on the back-end, and I wanted to build that as well. One of the many benchmarks I have for Objective-S is that it should be possible to build a nicer Rails with it. (At this point in time I am pretty sure I will hit that benchmark).

One of the ways to figure out if you have a good design is to stress-test it. One very useful stress-test is seeing how fast it can go, because that will tell you if the thing you built is lean, or if you put in unnecessary layers and indirections.

This is particularly interesting in a Scripted Components (pdf) system that combines a relatively slow but flexible interactive scripting language with fast, optimized components. The question is whether you can actually combine the flexibility of the scripting language while reaping the benefits of the fast components, rather than having to dive into adapting and optimizing the components for each use case, or just getting slow performance despite the fast components. My hunch was that the streaming approach I have been using for a while now and that worked really well for JSON and Objective-C would also do well in this more challenging setting.

Spoiler alert: it did!

The benchmark

The benchmark was a slightly modified version of the script that serves as a tasks backend. Like said sample script it also creates a tasks database and inserts some example rows. Instead of inserting two rows, it inserts 10 million. Or a hundred million.


#!env stsh
#-taskbench:dbref
#

class Task {
	var  id.
	var  done.
	var  title.
	-description { "". }
	+sqlForCreate {
		'( [id] INTEGER PRIMARY KEY, [title] VARCHAR(220) NOT NULL, [done] INTEGER );'.
	}
}.

scheme todo : MPWAbstractStore {
	var db.
	var tasksTable.
	-initWithRef:ref {
		this:db := (MPWStreamQLite alloc initWithPath:ref path).
		this:tasksTable :=  #MPWSQLTable{ #db: this:db , #tableClass: Task, #name: 'tasks'  }.
		this:db open.
		self.
	}
	-createTable {
		this:tasksTable create.
	    this:tasksTable := this:db tables at:'tasks'.
        this:tasksTable createEncoderMethodForClass: Task.
	}
	-createTaskListToInsert:log10ofSize {
		baseList ← #( #Task{  #title: 'Clean Room', #done: false }, #Task{  #title: 'Check Twitter', #done: true } ).
		...replicate ...
		taskList.
	}
	-insertTasks {
	    taskList := self createTaskListToInsert:6.
		1 to:10 do: {
			this:tasksTable insert:taskList.
		}.
	}
}.
todo := todo alloc initWithRef:dbref.
todo createTable.
todo insertTasks.

(I have removed the body of the method that replicates the 2 tasks into the list of millions of tasks we need to insert. It was bulky and not relevant.)

In this sample we define the Task class and use that to create the SQL Table. We could also have simply created the table and generated a Tasks class from that.

Anyway, running this script yields the following result.


> time ./taskbench-sqlite.st /tmp/tasks1.db 
./taskbench-sqlite.st /tmp/tasks1.db  4.07s user 0.20s system 98% cpu 4.328 total
> ls -al  /tmp/tasks1.db* 
-rw-r--r--  1 marcel  wheel   214M Jul 24 20:11 /tmp/tasks1.db
> sqlite3 /tmp/tasks1.db 'select count(id) from tasks;' 
10000000

So we inserted 10M rows in 4.328 seconds, yielding several hundred megabytes of SQLite data. This would be 138M rows had we let it run for a minute. Nice. For comparison, the original article's numbers were 11M rows/minute for CPython, 40M rows/minute for PyPy and 181M rows/minute for Rust, though on a slower Intel MacBook Pro whereas I was running this on an M1 Air. I compiled and ran the Rust version on my M1 Air and it did 100M rows in 21 seconds, so just a smidgen over twice as fast as my Objective-S script, though with a simpler schema (CHAR(6) instead of VARCHAR(220)) and less data (1.5GB vs. 2.1GB for 100M rows).

Getting SQLite fast

The initial version of the script was far, far slower, and at first it was, er, "sub-optimal" use of SQLite that was the main culprit, mostly inserting every row by itself without batching. When SQLite sees an INSERT (or an UPDATE for that matter) that is not contained in a transaction, it will automatically wrap that INSERT inside a generated transaction and commit that transaction after the INSERT is processed. Since SQLite is very fastidious about ensuring that transactions get to disk atomically, this is slow. Very slow.

The class handling SQLite inserts is a Polymorphic Write Stream, so it knows what an array is. When it encounters one, it sends itself the beginArray message, writes the contents of the array and finishes by sending itself the endArray message. Since writing an array sort of implies that you want to write all of it, this was a good place to insert the transactions:


-(void)beginArray {
    sqlite3_step(begin_transaction);
    sqlite3_reset(begin_transaction);
}

-(void)endArray {
    sqlite3_step(end_transaction);
    sqlite3_reset(end_transaction);
}

So now, if you want to write a bunch of objects as a single transaction, just write them as an array, as the benchmark code does. There were some other minor issues, but after that less than 10% of the total time were spent in SQLite, so it was time to optimize the caller, my code.

Column keys and Cocoa Strings

At this point, my guess was that the biggest remaining slowdown would be my, er, "majestic" Objective-S interpreter. I was wrong, it was Cocoa string handling. Not only was I creating the SQLite parameter placeholder keys dynamically, so allocating new NSString objects for each column of each row, it also happens that getting character data from an NSString object nowadays involves some very complex and slow internal machinery using encoding conversion streams. -UTF8String is not your friend, and other methods appear to fairly consistently use the same slow mechanism. I guess making NSString horribly slow is one way to make other string handling look good in comparison.

After a few transformations, the code would just look up the incoming NSString key in a dictionary that mapped it to the SQLite parameter index. String-processing and character accessing averted.

Jitting the encoder method. Without a JIT

One thing you might have noticed about the class definition in the benchmark code is that there is no encoder method, it just defines its instance variables and some other utilities. So how is the class data encoded for the SQLTable? KVC? No, that would be a bit slow, though it might make a good fallback.

The magic is the createEncoderMethodForClass: method. This method, as the name suggests, creates an encoder method by pasting together a number of blocks, turns the top-level into a method using imp_implementationWithBlock(), and then finally adds that method to the class in question using class_addMethod().


-(void)createEncoderMethodForClass:(Class)theClass
{
    NSArray *ivars=[theClass allIvarNames];
    if ( [[ivars lastObject] hasPrefix:@"_"]) {
        ivars=(NSArray*)[[ivars collect] substringFromIndex:1];
    }
    
    NSMutableArray *copiers=[[NSMutableArray arrayWithCapacity:ivars.count] retain];
    for (NSString *ivar in ivars) {
        MPWPropertyBinding *accessor=[[MPWPropertyBinding valueForName:ivar] retain];
        [ivar retain];
        [accessor bindToClass:theClass];
        
        id objBlock=^(id object, MPWFlattenStream* stream){
            [stream writeObject:[accessor valueForTarget:object] forKey:ivar];
        };
        id intBlock=^(id object, MPWFlattenStream* stream){
            [stream writeInteger:[accessor integerValueForTarget:object] forKey:ivar];
        };
        int typeCode = [accessor typeCode];
        
        if ( typeCode == 'i' || typeCode == 'q' || typeCode == 'l' || typeCode == 'B' ) {
            [copiers addObject:Block_copy(intBlock)];
        } else {
            [copiers addObject:Block_copy(objBlock)];
        }
    }
    void (^encoder)( id object, MPWFlattenStream *writer) = Block_copy( ^void(id object, MPWFlattenStream *writer) {
        for  ( id block in copiers ) {
            void (^encodeIvar)(id object, MPWFlattenStream *writer)=block;
            encodeIvar(object, writer);
        }
    });
    void (^encoderMethod)( id blockself, MPWFlattenStream *writer) = ^void(id blockself, MPWFlattenStream *writer) {
        [writer writeDictionaryLikeObject:blockself withContentBlock:encoder];
    };
    IMP encoderMethodImp = imp_implementationWithBlock(encoderMethod);
    class_addMethod(theClass, [self streamWriterMessage], encoderMethodImp, "v@:@" );
}

What's kind of neat is that I didn't actually write that method for this particular use-case: I had already created it for JSON-coding. Due to the fact that the JSON-encoder and the SQLite writer are both Polymorphic Write Streams (as are the targets of the corresponding decoders/parsers), the same method worked out of the box for both.

(It should be noted that this encoder-generator currently does not handle all variety of data types; this is intentional).

Getting the data out of Objective-S objects

The encoder method uses MPWPropertyBinding objects to efficiently access the instance variables via the object's accessors, caching IMPs and converting data as necessary, so they are both efficient and flexible. However, the actual accessors that Objective-S generated for its instance variables were rather baroque, because they used the same basic mechanism used for Objective-S methods, which can only deal with objects, not with primitive data types.

In order to interoperate seamlessly with Objective-C, which expected methods that can take data types other than objects, all non-object method arguments are converted to objects on the way in, and return values are converted from objects to primitive values on the way out.

So even the accessors for primitive types such as the integer "id" or the boolean "done" would have their values converted to and from objects by the interface machinery. As I noted above, I was a bit surprised that this inefficiency was overshadowed by the NSString-based key handling.

In fact, one of the reason for pursuing the SQLite insert benchmark was to have a reason for finally tackling this Rube-Goldberg mechanism. In the end, actually addressing it turned out to be far less complex than I had feared, with the technique being very similar to that used for the encoder-generator above, just simpler.

Depending on the type, we use a different block that gets parameterised with the offset to the instance variable. I show the setter-generator below, because there the code for the object-case is actually different due to retain-count handling:


#define pointerToVarInObject( type, anObject ,offset)  ((type*)(((char*)anObject) + offset))

#ifndef __clang_analyzer__
// This leaks because we are installing into the runtime, can't remove after

-(void)installInClass:(Class)aClass
{
    SEL aSelector=NSSelectorFromString([self objcMessageName]);
    const char *typeCode=NULL;
    int ivarOffset = (int)[ivarDef offset];
    IMP getterImp=NULL;
    switch ( ivarDef.objcTypeCode ) {
        case 'd':
        case '@':
            typeCode = "v@:@";
            void (^objectSetterBlock)(id object,id arg) = ^void(id object,id arg) {
                id *p=pointerToVarInObject(id,object,ivarOffset);
                if ( *p != arg ) {
                    [*p release];
                    [arg retain];
                    *p=arg;
                }
            };
            getterImp=imp_implementationWithBlock(objectSetterBlock);
            break;
        case 'i':
        case 'l':
        case 'B':
            typeCode = "v@:l";
            void (^intSetterBlock)(id object,long arg) = ^void(id object,long arg) {
                *pointerToVarInObject(long,object,ivarOffset)=arg;
            };
            getterImp=imp_implementationWithBlock(intSetterBlock);
            break;
        default:
            [NSException raise:@"invalidtype" format:@"Don't know how to generate set accessor for type '%c'",ivarDef.objcTypeCode];
            break;
    }
    if ( getterImp && typeCode ) {
        class_addMethod(aClass, aSelector, getterImp, typeCode );
    }
    
}

At this point, profiles were starting to approach around two thirds of the time being spent in sqlite_ functions, so the optimisation efforts were starting to get into a region of diminishing returns.

Linear scan beats dictionary

One final noticeable point of obvious overhead was the (string) key to parameter index mapping, which the optimizations above had left at a NSDictionary mapping from NSString to NSNumber. As you probably know, NSDictionary isn't exactly the fastest. One idea was to replace that lookup with a MPWFastrStringTable, but that means either needing to solve the problem of fast access to NSString character data or changing the protocol.

So instead I decided to brute-force it: I store the actual pointers to the NSString objects in a C-Array indexed by the SQLite parameter index. Before I do the other lookup, which I keep to be safe, I do a linear scan in that table using the incoming string pointer. This little trick largely removed the parameter index lookup from my profiles.

Conclusion

With those final tweaks, the code is probably quite close to as fast as it is going to get. Its slower performance compared to the Rust code can be attributed to the fact that it is dealing with more data and a more complex schema, as well as having to actually obtain data from materialized objects, whereas the Rust code just generates the SQlite calls on-the-fly.

All this is achieved from a slow, interpreted scripting language, with all the variable parts (data class, steering code) defined in said slow scripting language. So while I look forward to the native compiler for Objective-S, it is good to know that it isn't absolutely necessary for excellent performance, and that the basic design of these APIs is sound.

Sunday, June 21, 2020

Beyond Faster JSON Support for iOS/macOS, Part 9: CSV and SQLite

When looking at the MPWPlistStreaming protocol that I've been using for my JSON parsing series, one thing that was probably noticeable is that it isn't particularly JSON-focused. In fact, it wasn't even initially designed for parsing, but for generating.

So could we use this for other de-serialization tasks? Glad you asked!

CSV parsing

One of the examples in my performance book involves parsing Comma Separated Values quickly, within the context of getting the time to convert a 139Mb GTFS file to something usable on the phone down from 20 minutes using using CoreData/SQLite to slightly less than a second using custom in-memory data structures that are also several orders of magnitude faster to query on-device.

The original project's CVS parser took around 18 seconds, which wasn't a significant part of the 20 minutes, but when the rest only took a couple of hundred milliseconds, it was time to make that part faster as well. The result, slightly generalized, is MPWDelimitedTable ( .h .m ).

The basic interface is block-based, with the block being called for every row in the table, called with a dictionary composed of the header row as keys and the contents of the row as values.


-(void)do:(void(^)(NSDictionary* theDict, int anIndex))block;

Adapting this to the MPWPlistStreaming protocol is straightforward:
-(void)writeOnBuilder:(id )builder
{
    [builder beginArray];
    [self do:^(NSDictionary* theDict, int anIndex){
        [builder beginDictionary];
        for (NSString *key in self.headerKeys) {
            [builder writeObject:theDict[key] forKey:key];
        }
        [builder endDictionary];
    }];
    [builder endArray];
}

This is a quick-and-dirty implementation based on the existing API that is clearly sub-optimal: the API we call first constructs a dictionary from the row and the header keys and then we iterate over it. However, it works with our existing set of builders and doesn't build an in-memory representation of the entire CSV.

It will also be relatively straightforward to invert this API usage, modifying the low-level API to use MPWPlistStreaming and then creating a higher-level block- and dictionay-based API on top of that, in a way that will also work with other MPWPlistStreaming clients.

SQLite

Another tabular data format is SQL data bases. On macOS/iOS, one very common database is SQLite, usually accessed via CoreData or the excellent and much more light-weight fmdb.

Having used fmdb myself before, and bing quite delighted with it, my first impulse was to write a MPWPlistStreaming adapter for it, but after looking at the code a bit more closely, it seemed that it was doing quite a bit that I would not need for MPWPlistStreaming.

I also think I saw the same trade-off between a convenient and slow convenience based on NSDictionary and a much more complex but potentially faster API based on pulling individual type values.

So Instead I decided to try and do something ultra simple that sits directly on top of the SQLite C-API, and the implementation is really quite simple and compact:


@interface MPWStreamQLite()

@property (nonatomic, strong) NSString *databasePath;

@end

@implementation MPWStreamQLite
{
    sqlite3 *db;
}

-(instancetype)initWithPath:(NSString*)newpath
{
    self=[super init];
    self.databasePath = newpath;
    return self;
}

-(int)exec:(NSString*)sql
{
    sqlite3_stmt *res;
    int rc = sqlite3_prepare_v2(db, [sql UTF8String], -1, &res, 0);
    @autoreleasepool {
        [self.builder beginArray];
        int step;
        int numCols=sqlite3_column_count(res);
        NSString* keys[numCols];
        for (int i=0;i < numCols; i++) {
            keys[i]=@(sqlite3_column_name(res, i));
        }
        while ( SQLITE_ROW == (step = sqlite3_step(res))) {
            @autoreleasepool {
                [self.builder beginDictionary];
                for (int i=0; i < numCols; i++) {
                    const char *text=(const char*)sqlite3_column_text(res, i);
                    if (text) {
                        [self.builder writeObject:@(text) forKey:keys[i]];
                    }
                }
                [self.builder endDictionary];
            }
        }
        sqlite3_finalize(res);
        [self.builder endArray];
    }
    return rc;
}

-(int)open
{
    return sqlite3_open([self.databasePath UTF8String], &db);
}

-(void)close
{
    if (db) {
        sqlite3_close(db);
        db=NULL;
    }
}


Of course, this doesn't do a lot, chiefly it only reads, no updates, inserts or deletes. However, the code is striking in its brevity and simplicity, while at the same time being both convenient and fast, though with still some room for improvement.

In my experience, you tend to not get all three of these properties at the same time: code that is simple and convenient tends to be slow, code that is convenient and fast tends to be rather tricky and code that's simple and fast tends to be inconvenient to use.

How easy to use is it? The following code turns a table into an array of dictionaries:


#import <MPWFoundation/MPWFoundation.h>

int main(int argc, char* argv[]) {
   MPWStreamQLite *db=[[MPWStreamQLite alloc] initWithPath:@"chinook.db"];
   db.builder = [MPWPListBuilder new];
   if( [db open] == 0 ) {
       [db exec:@"select * from artists;"];
       NSLog(@"results: %@",[db.builder result]);
       [db close];
   } else {
       NSLog(@"Can't open database: %s\n", [db error]);
   }
   return(0);
}

This is pretty good, but probably roughly par for the course for returning a generic data structure such as array of dictionaries, which is not going to be particularly efficient. (One of my first clues that CoreData's predecessor EOF wasn't particularly fast was when I read that fetching raw dictionaries was an optimization, much faster than fetching objects.)

What if we want to get objects instead? Easy, just replace the MPWPListBuilder with an MPWObjectBuilder, parametrized with the class to create. Well, and define the class, but presumably you already havee that if the task is to convert to objects of that class. And it cold obviously also be automated.



#import <MPWFoundation/MPWFoundation.h>

@interface Artist : NSObject { }

@property (assign) long ArtistId;
@property (nonatomic,strong) NSString *Name;

@end

@implementation Artist

-(NSString*)description
{
	return [NSString stringWithFormat:@"<%@:%p id: %ld name: %@>",[self class],self,self.ArtistId,self.Name];
}

@end

int main(int argc, char* argv[]) {
   MPWStreamQLite *db=[[MPWStreamQLite alloc] initWithPath:@"chinook.db"];
   db.builder = [[MPWObjectBuilder alloc] initWithClass:[Artist class]];
   if( [db open] == 0) {
       [db exec:@"select * from artists"];
       NSLog(@"results: %@",[db.builder result]);
       [db close];
   } else {
       NSLog(@"Can't open database: %s\n", [db error]);
   }
   return(0);
}

Note that this does not generate a plist representation as an intermediate step, it goes straight from database result sets to objects. The generic intermediate "format" is the MPWPlistStreaming protocol, which is a dematerialized representation, both plist and objects are peers.

TOC

Somewhat Less Lethargic JSON Support for iOS/macOS, Part 1: The Status Quo
Somewhat Less Lethargic JSON Support for iOS/macOS, Part 2: Analysis
Somewhat Less Lethargic JSON Support for iOS/macOS, Part 3: Dematerialization
Equally Lethargic JSON Support for iOS/macOS, Part 4: Our Keys are Small but Legion
Less Lethargic JSON Support for iOS/macOS, Part 5: Cutting out the Middleman
Somewhat Faster JSON Support for iOS/macOS, Part 6: Cutting KVC out of the Loop
Faster JSON Support for iOS/macOS, Part 7: Polishing the Parser
Faster JSON Support for iOS/macOS, Part 8: Dematerialize All the Things!
Beyond Faster JSON Support for iOS/macOS, Part 9: CSV and SQLite

Thursday, May 14, 2020

Embedding Objective-Smalltalk

Ilja just asked for embedded scripting-language suggestions, presumably for his GarageSale E-Bay listings manager, and so of course I suggested Objective-Smalltalk.

Unironically :-)

This is a bit scary. On the one hand, Objective-Smalltalk has been in use in my own applications for well over a decade and runs the http://objective.st site, both without a hitch and the latter shrugging of a Hacker News "Hug of Death" without even the hint of glitch. On the other hand, well, it's scary.

As for usability, you include two frameworks in your application bundle, and the code to start up and interact with the interpreter or interpreters is also fairly minimal, not least of all because I've been doing so in quite a number of applications now, so inconvenience gets whittled away over time.

In terms of suitability, I of course can't answer that except for saying it is absolutely the best ever. I can also add that another macOS embeddable Smalltalk, FScript, was used successfully in a number of products. Anyway, Ilja was kind enough to at least pretend to take my suggestion seriously, and responded with the following question as to how code would look in practice:

I am only too happy to answer that question, but the answer is a bit beyond the scope of twitter, hence this blog post.

First, we can keep things very close to the original, just replacing the loop with a -select: and of course changing the syntax to Objective-Smalltalk.


runningListings := context getAllRunningListings.
listingsToRelist := runningListings select:{ :listing |
    listing daysRunning > 30 and: listing watchers < 3 .
}
ebay endListings:listingsToRelist ended:{ :ended | 
     ebay relistListings:ended relisted: { :relisted |
         ui alert:"Relisted: {relisted}".
     }
}

Note the use of "and:" instead of "&&" and the general reduction of sigils. Although I personally don't like the pyramid of doom, the keyword message syntax makes it significantly less odious.

So much in fact, that Swift recently adopted open keyword syntax for the special case of multiple trailing closures. Of course the mind boggles a bit, but that's a topic for a separate post.

So how else can we simplify? Well, the context seems a little unspecific, and getAllRunningListings a bit specialized, it probably has lots of friends that result from mapping a website with lots of resources onto a procedural interface.

Let's instead use URLs for this, so an ebay: scheme that encapsulates the resources that EBay lets us play with.


listingsToRelist := ebay:listings/running select:{ :listing |
    listing daysRunning > 30 and: listing watchers < 3 .
}
ebay endListings:listingsToRelist ended:{ :ended | 
     ebay relistListings:ended relisted: { :relisted |
         ui alert:"Relisted {relisted} listings".
     }
}

I have to admit I also don't really understand the use of callbacks in the relisting process, as we are waiting for everything to complete before moving to the next stage. So let's just implement this as plain sequential code:
listingsToRelist := ebay:listings/running select:{ :listing |
    listing daysRunning > 30 and: listing watchers < 3 .
}
ended := ebay endListings:listingsToRelist.
relisted := ebay relistListings:ended.
ui alert:"Relisted: {relisted}".

(In scripting contexts, Objective-Smalltalk currently allows defining variables by assigning to them. This can be turned off.)

However, it seems odd and a bit non-OO that the listings shouldn't know how to do stuff, so how about just having relist and end be methods on the listings themselves? That way the code simplifies to the following:


listingsToRelist := ebay:listings/running select:{ :listing |
    listing daysRunning > 30 and: listing watchers < 3 .
}
ended := listingsToRelist collect end.
relisted := ended collect relist.
ui alert:"Relisted: {relisted}".

If batch operations are typical, it probably makes sense to have a listings collection that understands about those operations:
listingsToRelist := ebay:listings/running select:{ :listing |
    listing daysRunning > 30 and: listing watchers < 3 .
}
ended := listingsToRelist end.
relisted := ended relist.
ui alert:"Relisted: {relisted}".

Here I am assuming that ending and relisting can fail and therefore these operations need to return the listings that succeeded.

Oh, and you might want to give that predicate a name, which then makes it possible to replace the last gobbledygook with a clean, "do what I mean" Higher Order Message. Oh, and since we've had Unicode for a while now, you can also use '←' for assignment, if you want.


extension EBayListing {
  -<bool>shouldRelist {
      self daysRunning > 30 and: self watchers < 3.
  }
}

listingsToRelist ← ebay:listings/running select shouldRelist.
ended ← listingsToRelist end.
relisted ← ended relist.
ui alert:"Relisted: {relisted}".

To my obviously completely unbiased eyes, this looks pretty close to a high-level, pseudocode specification of the actions to be taken, except that it is executable.

This is a nice step-by-step script, but with everything so compact now, we can get rid of the temporary variables (assuming the extension) and make it a one-liner (plus the alert):


relisted ← ebay:listings/running select shouldRelist end relist.
ui alert:"Relisted: {relisted}".

It should be noted that the one-liner came to be not as a result of sacrificing readability in order to maximally compress the code, but rather as an indirect result of improving readability by removing the cruft that's not really part of the problem being solved.

Although not needed in this case (the precedence rules of unary message sends make things unambiguous) some pipe separators may make things a bit more clear.


relisted ← ebay:listings/running select shouldRelist | end | relist.
ui alert:"Relisted: {relisted}".

Whether you prefer the one-liner or the step-by-step is probably a matter of taste.

Friday, April 24, 2020

Faster JSON Support for iOS/macOS, Part 7: Polishing the Parser

A convenient setback

One thing that you may have noticed last time around was that we were getting the instance variable names from the class, but then also still manually setting the common keys manually. That's a bit of duplicated and needlessly manual effort, because the common keys are exactly those ivar names.

However, the two pieces of information are in different places, the ivar names in the builder and the common strings in the in the parse itself. One way of consolidating this information is by creating a convenience intializer for decoding to objects as follows:



-initWithClass:(Class)classToDecode
{
    self = [self initWithBuilder:[[[MPWObjectBuilder alloc] initWithClass:classToDecode] autorelease]];
    [self setFrequentStrings:(NSArray*)[[[classToDecode ivarNames] collect] substringFromIndex:1]];
    return self;
}

We still compute the ivar names twice, but that's not really such a big deal, so something we can fix later, just like the issue that we should probably be using property names instead of instance variable names that in the case of properties we have to post-process to get rid of the underscores added by ivar synthesis.

With that, the code to parse to objects simplifies to the following, very similar to what you would see in Swift with JSONDecoder.


-(void)decodeMPWDirect:(NSData*)json
{
    MPWMASONParser *parser=[[MPWMASONParser alloc] initWithClass:[TestClass class]];
    NSArray* objResult = [parser parsedData:json];
}

So, quickly verifying that performance is still the same (always do this!) and...oops! Performance dropped significantly, from 441ms to over 700ms. How could such an innocuous change lead to a 50% performance regression?

The profile shows that we are now spending significantly more time in MPWSmallStringTable's objectForKey: method, where it gets the bytes out of the NSString/CFString, but why that should be the case is a bit mysterious, since we changed virtually nothing.

A little further sleuthing revealed that the strings in question are now instances of NSTaggedPointerString, where previously they were instances of __NSCFConstantString. The latter has a pointer to its byte-oriented character orientation, which it can simply return, while the former cleverly encodes the characters in the pointer itself, so it first has to reconstruct that byte representation. The method of constructing that representation and computing the size of such a representation also appears to be fairly generic and slow via a stream.

This isn't really easy to solve, since the creation of NSTaggedPointerStrring instances is hardwired pretty deep in CoreFoundation with no way to disable this "optimization". Although it would be possible to create a new NSString subclass with a byte buffer, make sure to convert to that class before putting instances in the lookup table, that seems like a lot of work. Or we could just revert this convenience.

Damn the torpedoes and full speed ahead!

Alternatively, we really wanted to get rid of this whole process of packing character data into NSString instances just to immediately unpack them again, so let's leave the regression as is and do that instead.

Where previously the builder had a NSString *key instance vaiable, it now has a char *keyStr and a int keyLen. The string-handling case in the JSON parser is now split betweeen the key and the non-key casse, with the non-key case still doing the conversion, but the key-case directly sending the char* and length to the builder.


			case '"':
                parsestring( curptr , endptr, &stringstart, &curptr  );
				if ( curptr[1] == ':' ) {
                    [_builder writeKeyString:stringstart length:curptr-stringstart];
					curptr++;
					
				} else {
                    curstr = [self makeRetainedJSONStringStart:stringstart length:curptr-stringstart];
					[_builder writeString:curstr];
				}
                curptr++;
				break;

This means that at least temporarily, JSON escape handling is disabled for keys. It's straightforward to add back, makeRetainedJSONStringStart:length: does all its processing in a character buffer, only converting to a string object at the very end.


-(void)writeString:(NSString*)aString
{
    if ( keyStr ) {
        MPWValueAccessor *accesssor=OBJECTFORSTRINGLENGTH(self.accessorTable, keyStr, keyLen);
        [accesssor setValue:aString forTarget:*tos];
        keyStr=NULL;
    } else {
        [self pushObject:aString];
    }
}

If there is a key, we are in a dictionary, otherwise an array (or top-level). In the dictionary case, we can now fetch the ValueAccessor via the OBJECTFORSTRINGLENGTH() macro.

The results are encouraging: 299ms, or 147 MB/s.

The MPWPlistBuilder also needs to be adjusted: as it builds and NSDictionary and not an object, it actually needs the NSString key, but the parser no longer delivers those. So it just creates them on the fly:


-(NSString*)key
{
    NSString *key=nil;
    if ( keyStr) {
        if ( _commonStrings ) {
            key=OBJECTFORSTRINGLENGTH(_commonStrings, keyStr, keyLen);
        }
        if ( !key ) {
            key=[[[NSString alloc] initWithBytes:keyStr length:keyLen encoding:NSUTF8StringEncoding] autorelease];
        }
    }
    return key;
}

Surprisingly, this makes the dictionary parsing code slightly faster, bringing up to par with NSSJSSONSerialization at 421ms.

Eliminating NSNumber

Our use of NSNumber/CFNumber values is very similar to our use of NSString for keys: the parser wraps the parsed number in the object, the builder then unwraps it again.

Changing that, initially just for integers, is straightforward: add an integer-valued message to the builder protocol and implement it.


-(void)writeInteger:(long)number
{
    if ( keyStr ) {
        MPWValueAccessor *accesssor=OBJECTFORSTRINGLENGTH(_accessorTable, keyStr, keyLen);
        [accesssor setIntValue:number forTarget:*tos];
        keyStr=NULL;
    } else {
        [self pushObject:@(number)];
    }
}

The actual integer parsing code is not in MPWMASONParser but its superclasss, and as we don't want to touch that for now, let's just copy-paste that code, modifying it to return a C primitive type instead of an object.


-(long)longElementAtPtr:(const char*)start length:(long)len
{
    long val=0;
    int sign=1;
    const char *end=start+len;
    if ( start[0] =='-' ) {
        sign=-1;
        start++;
    } else if ( start[0]=='+' ) {
        start++;
    }
    while ( start < end && isdigit(*start)) {
        val=val*10+ (*start)-'0';
        start++;
    }
    val*=sign;
    return val;
}

I am sure there are better ways to turn a string into an int, but it will do for now. Similarly to the key/string distinction, we now special case integers.
                if ( isReal) {
                    number = [self realElement:numstart length:curptr-numstart];

                    [_builder writeString:number];
                } else {
                    long n=[self longElementAtPtr:numstart length:curptr-numstart];
                    [_builder writeInteger:n];
                }

Again, not pretty, but we can clean it up later.

Together with using direct instance variable access instead of properties to get to the accessorTable, this yields a very noticeable speed boost:

229 ms, or 195 MB/s.

Nice.

Discussion

What happened here? Just random hacking on the profile and replacing nice object-oriented programming with ugly but fast C?

Although there is obviously some truth in that, profiles were used and more C primitive types appeared, I would contend that what happened was a move away from objects, and particularly away from generic and expensive Foundation objects ("Foundation oriented programming"?) towards message oriented programming.

I'm sorry that I long ago coined the term "objects" for this topic because it gets many people to focus on the lesser idea.

The big idea is "messaging" -- that is what the kernal of Smalltalk/Squeak is all about (and it's something that was never quite completed in our Xerox PARC phase). The Japanese have a small word -- ma -- for "that which is in between" -- perhaps the nearest English equivalent is "interstitial". The key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be.

It turns out that message oriented programming (or should we call it Protocol Oriented Programming?) is where Objective-C shines: coarse-grained objects, implemented in C, that exchange messages, with the messages also as primitive as you can get away with. That was the idea, and when you follow that idea, Objective-C just hums, you get not just fast, but also flexible and architecturally nicely decoupled objects: elegance.

The combination of objects + primitive messages is very similar to another architecturally elegant and productive style: Unix pipes and filters. The components are in C and can have as rich an internal structure as you want, but they have to talk to each other via byte-streams. This can also be made very fast, and also prevents or at least reduces coupling between the components.

Another aspect is the tension between an API for use and an API for reuse, particularly within the constraints of call/return. When you get tasked with "Create a component + API for parsing JSON", something like NSJSONSerialization is something you almost have to come up with: feed it JSON, out comes parsed JSON. Nothing could be more convenient to use for "parsing JSON".

MPWMASONParser on the other hand is not convenient at all when viewed in isolation, but it's much more capable of being smoothly integrated into a larger processing chain. And most of the work that NSJSONSerialization did in the name of convenience is now just wasted, it doesn't make further processing any easier but sucks up enormous amounts of time.

Anyway, let's look at the current profile:

First, times are now small enough that high-resolution (100µs) sampling is now necessary to get meaningful results. Second, the NSNumber/CFNumber and NSString packing and unpacking is gone, with an even bigger chunk of the remaining time now going to object creation. objc_msgSend() is now starting to actually become noticeable, as is the (inefficient) character level parsing. The accessors of our test objects start to appear, if barely.

With the work we've done so far, we've improved speed around 5x from where we started, and at 195 MB/s are almost 20x faster than Swift's JSONDecoder.

Can we do better? Stay tuned.

Note

I can help not just Apple, but also you and your company/team with performance and agile coaching, workshops and consulting. Contact me at info at metaobject.com.

TOC

Somewhat Less Lethargic JSON Support for iOS/macOS, Part 1: The Status Quo
Somewhat Less Lethargic JSON Support for iOS/macOS, Part 2: Analysis
Somewhat Less Lethargic JSON Support for iOS/macOS, Part 3: Dematerialization
Equally Lethargic JSON Support for iOS/macOS, Part 4: Our Keys are Small but Legion
Less Lethargic JSON Support for iOS/macOS, Part 5: Cutting out the Middleman
Somewhat Faster JSON Support for iOS/macOS, Part 6: Cutting KVC out of the Loop
Faster JSON Support for iOS/macOS, Part 7: Polishing the Parser
Faster JSON Support for iOS/macOS, Part 8: Dematerialize All the Things!
Beyond Faster JSON Support for iOS/macOS, Part 9: CSV and SQLite

Monday, April 20, 2020

Somewhat Faster JSON Support for iOS/macOS, Part 6: Cutting KVC out of the Loop

Last time, we actually made some significant headway by taking advantage of the dematerialisation of the plist intermediate representation. So instead of first producing an array of dictionaries, we went directly from JSON to the final object representation.

This got us down from around 1.1 seconds to a little over 600 milliseconds.

It was accomplished by using the Key Value Coding method setValue:forKey: to directly set the attributes of the objects from the parsed JSON. Oh, and instantiating those objects in the first place, instead of dictionaries.

That this should be so much faster than most other methods, for example beating Swift's JSONDecoder() by a cool 7x, is a little surprising, given that KVC is, as I mentioned in the first article of the series, the slowest mechanism for getting data in and out of objcets short of deliberate Rube Goldber Mechanisms.

What is KVC and why is it slow?

Key Value Coding was a core part of NeXT's Enterprise Object Framework, introduced in 1994.
Key-value coding is a data access mechanism in which the properties of an object are accessed indirectly by key or name, rather than directly as fields or by invocation of accessor methods. It is used throughout Enterprise Objects but is perhaps most useful to you when accessing data in relationships between enterprise objects.

Key-value coding enables the use of keypaths to traverse relationships. For example, if a Person entity has a relationship called toPhoto whose destination entity (called PersonPhoto) contains an attribute called photo, you could access that data by traversing the keypath toPhoto.photo from within a Person object.

Keypaths are just one way key-value coding is an invaluable feature of Enterprise Objects. In general, though, it is most useful in providing a consistent way to access an object's data. Rather than needing to know if an object's data members have accessor methods, what the names of those accessor methods are, or if the data is accessible through fields, all you need to know are the keys that represent an object’s data. Key-value coding automatically finds the data, regardless of how the object provides its data. In this context, key-value coding satisfies the classic design pattern principle to “encapsulate the things that varies.”

It still is an extremely powerful programming technique that lets us write algorithms that work generically with any object properties, and is currently the basis for CoreData, AppleScript support, Key Value Observing and Bindings. (Though I am somewhat skeptical of some of these, not least for performance reasons, see The Siren Call of KVO and (Cocoa) Bindings). It was also part of the inspiration for Polymorphic Identifiers.

The core of KVC are the valueForKey: and setValue:forKey: messages, which have default implementations in NSObject. These default implementations take the NSString key, derive an accessor message from that key and then send the message, either setting or returning a value. If the value that the underlying message takes/returns is a non-object type, then KVC wraps/unwraps as necessary.

If this sounds expensive, then that's because it is. To derive the set accessor from the key, the first character of the key has to be capitalized, the the string "set" prepended and the string converted to an Objective-C selector (SEL). In theory, this has to be done on every call to one of the KVC methods, and it has to be done with NSString objects, which do a fantastic job of representing human-visible text, but are a bit heavy-weight for low-level work.

Doing the full computation on every invocation would be way too expensive, so Apple caches some of the intermediate results. As there is no obvious place to put those intermediate results, they are placed in global hash tables, keyed by class and property/key name. However, even those lookups are still significantly more expensive than the final set or get property accesss, and we have to do multiple lookups. Since theses tables have to be global, locking is also required.

ValueAccessor

All this expense could be avoided if we had a custom object to mediate the access, rather than a naked NSString. That object could store those computed values, and then provide fast and generic access to arbitrary properties. Enter MPWValueAccesssor (.h .m).

A word of warning: unlike MPWStringtable, MPWValueAccesssor is mostly experimental code. It does have tests and largely works, but it is incomplete in many ways and also contains a bunch of extra and probably extraneous ideas. It is sufficient for our current purpose.

The core of this class is the AccessPathComponent struct.


typedef struct {
    Class   targetClass;
    int     targetOffset;
    SEL     getSelector,putSelector;
    IMP0    getIMP;
    IMP1    putIMP;
    id      additionalArg;
    char    objcType;
} AccessPathComponent;

This struct contains a number of different ways of getting/setting the data:
  1. the integer offset into the object where the ivar is located
  2. a pair of Objective-C selectors/message names, one for getting, one for setting.
  3. a pair of function pointers to the Objective-C methods that the respective selectors resolve to
  4. the additional arg is the key, to be used for keyed access
The getIMP and putImp are initialized to objc_msgSend(), so they can always be used. If we bind the ValueAccessor to a class, those function pointers get resolved to the actual getter/setter methods. In addition the objcType gets set to the type of the instance variable, so we can do automatic conversions like KVC. (This was some code I actually had to add between the last instalment and the current one.)

The key takeaway is that all the string processing and lookup that KVC needs to do on every call is done once during initialization, after that it's just a few messages and/or pre-resolved function calls.

Hooking up the ValueAccessor

Adapting the MPWObjectBuilder (.h .m) to use MPWValueAccessor was much easier than I had expected. Thee following shows the changes made:
@property (nonatomic, strong) MPWSmallStringTable *accessorTable;

...

-(void)setupAcceessors:(Class)theClass
{
    NSArray *ivars=[theClass ivarNames];
    ivars=[[ivars collect] substringFromIndex:1];
    NSMutableArray *accessors=[NSMutableArray arrayWithCapacity:ivars.count];
    for (NSString *ivar in ivars) {
        MPWValueAccessor *accessor=[MPWValueAccessor valueForName:ivar];
        [accessor bindToClass:theClass];
        [accessors addObject:accessor];
    }
    MPWSmallStringTable *table=[[[MPWSmallStringTable alloc] initWithKeys:ivars values:accessors] autorelease];
    self.accessorTable=table;
}

-(void)writeObject:anObject forKey:aKey
{
    MPWValueAccessor *accesssor=[self.accessorTable objectForKey:aKey];
    [accesssor setValue:anObject forTarget:*tos];
}



The bulk of the changes come as part of the new -setupAccessors: method. It first asks the class what its instance variables are, creates a value accessor for that instance variabl(-name), binds the accessor to the class and finally puts the accessors in a lookup table keyed by name.

The -writeObject:forKey: method is modified to look up and use a value accessor instead of using KVC.

Results

The parsing driver code didn't have to be changed, re-running it on our non-representative 44 MB JSON file yields the following time:

441 ms.

Now we're really starting to get somewhere! This is just shy of 100 MB/s and 10x faster then Swift's JSONDecoder, and within 5% of raw NSJSONSerialization.

Analysis and next steps

Can we do better? Why yes, glad you asked. Let's have a look at the profile.

First thing to note is that object-creation (beginDictionary) is now the #1 entry under the parse, as it should be. This is another indicator that we are not just moving in the right direction, but also closing in on the endgame.

However, there is still room for improvement. For example, although actually searching the SmallStringTable for the ValueAccessor (offsetOfCStringWithLengthInTableOfLength()) takes only 2.7% of the time, about the same as getting the internal char* out of a CFString via the fast-path (CFStringGetCStringPtr()), the total time for the -objectForKey: is a multiple of that, at 13%. This means that unwrapping the NSString takes more time than doing the actual work. Wrapping the char* and length into an NSString also takes significant time, and all of this work is redundant...we would be better of just passing along the char* and length.

A similar wrap/unwrap situation occurs with integers, which we first turn into NSNumbers, only to immediately get the integer out again so we can set it.

objc_msgSend() also starts getting noticeable, so looking at a bit of IMP-caching and just eliminating unnecessary indirection also seems like a good idea.

That's another aspect of optimization work: while the occasional big win is welcome, getting to truly outstanding performance means not being satisfied with that, but slogging through all the small-ish seeming detail.

Note

I can help not just Apple, but also you and your company with performance and agile coaching, workshops and consulting. Contact me at info at metaobject.com.

TOC

Somewhat Less Lethargic JSON Support for iOS/macOS, Part 1: The Status Quo
Somewhat Less Lethargic JSON Support for iOS/macOS, Part 2: Analysis
Somewhat Less Lethargic JSON Support for iOS/macOS, Part 3: Dematerialization
Equally Lethargic JSON Support for iOS/macOS, Part 4: Our Keys are Small but Legion
Less Lethargic JSON Support for iOS/macOS, Part 5: Cutting out the Middleman
Somewhat Faster JSON Support for iOS/macOS, Part 6: Cutting KVC out of the Loop
Faster JSON Support for iOS/macOS, Part 7: Polishing the Parser
Faster JSON Support for iOS/macOS, Part 8: Dematerialize All the Things!
Beyond Faster JSON Support for iOS/macOS, Part 9: CSV and SQLite

Thursday, November 14, 2019

Presenting (in) Objective-Smalltalk

2019 has been the year that I have started really talking about Objective-Smalltalk in earnest, because enough of the original vision is now in place.

My first talk was at the European Smalltalk User Group's (ESUG) annual conference in my old hometown of Cologne: (pdf)

This year's ESUG was was my first since Essen in 2001, and it almost seemed like a bit of a timewarp. Although more than half the talks were about Pharo, the subjects seemed mostly the same as back when: a bit of TDD, a bit of trying to deal with native threads (exactly the same issues I struggled with when I was doing the CocoaSqueak VM), a bit of 3D graphics that weren't any better than 3D graphics in other environments, but in Smalltalk.

One big topic was getting large (and very profitable) Smalltalk code-bases running on mobile devices such as iPhones. The top method was transpiling to JavaScript, another translating the VM code to JavaScript and then having that run off-the-shelf images. Objective-Smalltalk can also be put in this class, with a mix of interpretation and native compilation.

My second talk, I was at Germany's oldest Mac conference, Macoun in Frankfurt. The videos from there usually take a while, but here was a reaction:

"Anyone who wants a glimpse at the future should have watched @mpweiher's talk"

Aww, shucks, thanks, but I'll take it. :-)

I also had two papers accepted at SPLASH '19, one was Standard Object Out: Streaming Objects with Polymorphic Write Streams at the Dynamic Languages Symposium, the other was Storage Combinators at Onward!.

Anyway, one aspect of those talks that I didn't dwell on is that the presentations themselves were implemented in Objective-Smalltalk, in fact the definitions were Objective-Smalltalk expressions, complex object literals to be precise.

What follows is an abridged version of the ESUG presentation:


controller := #ASCPresentationViewController{
    #Name : 'ESUG Demo'.
    #Slides : #(

      #ASCChapterSlide { 
               #text : 'Objective-SmallTalk'.
               #subtitle : 'Marcel Weiher (@mpweiher)'
         }  ,

        #ASCBulletSlide{ 
             #title : 'Objective-SmallTalk'.
             #bullets : #( 
                'Embeddable SmallTalk language (Mac, iOS, Linux, Windows)',
                'Objective-C framework (peer/interop)',
                'Generalizes Objects+Messages to Components+Connectors',
                'Enable composition by solving Architectural Mismatch',
             )
        } ,
      #ASCBulletSlide{ 
             #title : 'The Gentle Tyranny of Call/Return'.
             #bullets : #( 
                'Feymnan: we name everything just a little wrong',
                'Multiparadigm: Procedural, OO and FP!',
                "Guy Steele: it's no longer about completion",
                "Oscar Nierstrasz: we were told we could just model the domain",
                "Andrew Black: good OO students antropmorphise the objects",
             )
        } ,

         #ProgramVsSystem { 
              #lightIntensities : #( 0.2 , 0.7 )
              
         }  ,


       #ASCSlideWithFigure{ 
             #delayInSeconds : 5.0.
             #title : 'Objects and Messages'.
             #bullets : #( 
                'Objective-C compatible semantics',
                'Interpreted and native-compiled',
                '"C" using type annotations',
                'Higher Order Messaging',
                'Framework-oriented development',
                'Full platform integration',
             )
        } ,
  

       #ASCBulletSlide{ 
             #title : 'Pipes and Filters'.
             #bullets : #( 
                'Polymorphic Write Streams (DLS ''19)',
                '#writeObject:anObject',
                'Triple Dispatch + Message chaining',
                'Asynchrony-agnostic',
                'Streaming / de-materialized objects',
                'Serialisation, PDF/PS (Squeak), Wunderlist, MS , To Do',
                'Outlook: filters generalise methods?',
            )
        } ,
 
       #ASCBulletSlide{ 
             #title : 'In-Process REST'.
             #bullets : #( 
                'What real large-scale networks use',
                'Polymorphic Identifiers',
                'Stores',
                'Storage Combinators',
                'Used in a number of applications',
             )
        } ,


       #ASCBulletSlide{ 
             #title : 'Polymorphic Identifiers'.
             #bullets : #( 
                'All identifiers are URIs',
                "var:hello := 'World!",
                'file:{env:HOME}/Downloads/site := http://objective.st',
                'slider setValueHolder: ref:var:celsius',
             )
        } ,

       #ASCBulletSlide{ 
             #title : 'Storage Combinators'.
             #bullets : #( 
                'Onward! ''19',
                'Combinator exposes + consumes REST interfaces',
                'Uniform interface (REST) enables pluggability',
                'Narrow, semantically tight interface enables intermediaries',
                '10x productivity/code improvments',
             )
        } ,


      #ImageSlide{ 
               #text : 'Simple Composed Store'.
               #imageURL : '/Users/marcel/Documents/Writing/Dissertation/Papers/StorageCombinators/disk-cache-json-aligned.png'.
               #xOffset : 2.0 .
               #imageScale : 0.8
         }  , 
      #ASCBulletSlide{ 
             #title : 'Outlook'.
             #bullets : #( 
                'Port Stores and Polymorphic Write Streams',
                'Documentation / Sample Code',
                'Improve native compiler',
                'Tooling (Debugger)',
                'You! (http://objective.st)',
             )
        }  ,


      #ASCChapterSlide { 
               #text : 'Q&A   http://objective.st'.
               #subtitle : 'Marcel Weiher (@mpweiher)'
         }  ,
      )
}. 


There are a number of things going on here:
  • Complex object literals
  • A 3D presentation framework
  • Custom behavior via custom classes
  • Framework-oriented programming
Let's look at these in turn.

Complex object literals

Objective-Smalltalk has literals for arrays (really: ordered collections) and dictionaries, like many other languages now. Array literals are taken from Smalltalk, with a hash and round braces: #(). Unlike other Smalltalks, entries are separated via commas, so #( 1,2,3) rather than #( 1 2 3 ). For dictionaries, I borrowed the curly braces from Objective-C, so #{}.

This gives us the ability to specify complex property lists directly in code. A common idiom in Mac/iOS development circles is to initialize objects from property lists, so something like the following:


presentation = [[MyPresentation alloc] initWithDictionary:aDictionary];

All complex object literals really do is add a little bit of syntactic support for this idiom, by noticing that the two respective character at the start of array and dictionay literals give us a space to put a name, a class name, between those two characters:


presentation := #MyPresentation{ ... };

This will parse the text between the curly brackets as a dictionary and then initialize a MyPresentation object with that dictionary using the exact -initWithDictionary: message given above. This may seem like a very minor convenience, and it is, but it actually makes it possible to simply write down objects, rather than having to write code that constructs objects. The difference is subtle but significant.

The benefit becomes more obvious once you have nested structures. A normal plist contains no specific class information, just arrays, dictionaries numbers and strings, and in the Objective-C example, that class information is provided externally, by passing the generic plist to a specific class instance.

(JSON has a similar problem, which is why I still prefer XML for object encoding.)

So either that knowledge must also be provided externally, for example by the implicit knowledge that all substructure is uniform, or custom mechanisms must be devised to encode that information inside the dictionaries or arrays. Ad hoc. Every single time.

Complex object identifiers create a common mechanism for this: each subdictionary or sub-array can be tagged with the class of the object to create, and there is a convenient and distinct syntax to do it.

A 3D presentation framework

One of the really cool wow! effects of Alan Kay's Squeak demos is always when he breaks through the expected boundaries of a presentation with slides and starts live programming and interactive sketching on the slide. The effect is verey similar to when characters break the "fourth wall", and tends to be strongest on the very jaded, who were previously dismissive of the whole presentation.

Alas, a drawback is that those presentations in Squeak tend to look a bit amateurish and cartoonish, not at all polished.

Along came the Apple SceneKit Team's presentations, which were done as Cocoa/SceneKit applications. Which is totally amazing, as it allows arbitrary programmability and integration with custom code, just like Alan's demos, but with a lot more polish.

Of course, an application like that isn't reusable, the effort is pretty high and interactivity low.

I wonder what we could do about that?

First: turn the presentation application into a framework (Slides3D). Second, drive that framework interactively with Objective-Smalltalk from my Workspace-like "Smalltalk" application: presentation.txt. After a bit of setup such as loading the framework (framework:Slides3D load.) and defining a few custom slide classes, it goes on to define the presentation using the literal shown above and then starts the presentation by telling the presentation controller to display itself in a window.


framework:Slides3D load.     
class ProgramVsSystem : ASCSlide {
   var code.
   var system.
   ...
}.
class ImageSlide : ASCSlide { 
     var text.
     var image.


      #ASCChapterSlide { 
               #text : 'Q&A   http://objective.st'.
               #subtitle : 'Marcel Weiher (@mpweiher)'
         }  ,
      )
}. 

controller := #ASCPresentationViewController{
    #Name : 'ESUG Demo'.
    #Slides : #(

      #ASCChapterSlide { 
               #text : 'Objective-SmallTalk'.
               #subtitle : 'Marcel Weiher (@mpweiher)'
         }  ,

       ...
      )
}. 
     
controller view openInWindow:'Objective-SmallTalk (ESUG 2019)'. 

Voilà: highly polished, programmatically driven presentations that I can edit interactively and with a somewhat convenient format. Of course, this is not a one-off for presentations: the same mechanism can be used to define other object hierarchise, including but not limited to interactive GUIs.

Framework-oriented programming

Which brings us to the method behind all this madness: the concept I call framework-oriented programming.

The concept is worth at least another article or two, but at its most basic boils down to: for goodness sake, put the bulk of your code in frameworks, not in an application. Even if all you are building is an application. One app that does this right is Xcode. On my machine, the entire app bundle is close to 10GB. But the actual Xcode binary in /Applications/Xcode.app/Contents/MacOS? 41KB. Yes, Kilobytes. And most of that is bookkeeping and boilerplate, it really just contains a C main() function, which I presume largely matches the one that Xcode generates.

Why?

Simple: an Apple framework (i.e.: a .framework bundle) is at least superficially composable, but a .app bundle is not. You can compose frameworks into bigger frameworks, and you can take a framework and use it in a different app. This is difficult to impossible with apps (and no, kludged-together AppleScript concoctions don't count).

And doing it is completely trivial: after you create an app project, just create a framework target alongside the app target, add that framework to the app and then add all code and resources to the framework target instead of to the app target. Except for the main() function. If you already have an app, just move the code to the framework target, making adjustments to bundle loading code (the relevant bundle is now the framework and no longer the app/main bundle). This is what I did to derive Slides3D from the WWDC 2013 SceneKit App.

What I've described so fa is just code packaging. If you also organize the actual code as an object-oriented framework, you will notice that with time it will evolve into a black-box framework, with objects that are created, configured and composed. This is somewhat tedious to do in the base language (see: creating Views programmatically), so the final evolutionary step is considered a DSL (Hello, SwiftUI!). However, most of this DSL tends to be just creating, configuring and connecting objects. In other words: complex object literals.

Thursday, November 7, 2019

Instant Builds

One of the goals I am aiming for in Objective-Smalltalk is instant builds and effective live programming.

A month ago, I got a package from an old school friend: my old Apple ][+, which I thought I had given as a gift, but he insisted had been a long-term loan. That machine featured 48KB of DRAM and a 1 MHz, 8 bit 6502 processor that took multiple cycles for even the simplest instructions, had no multiply instructions and almost no registers. Yet, when I turn it on it becomes interactive faster than the CRT warms up, and the programming experience remains fully interactive after that. I type something in, it executes. I change the program, type "RUN" and off it goes.

Of course, you can also get that experience with more complex systems, Smalltalk comes to mind, but the point is that it doesn't take the most advanced technology or heroic effort to make systems interactive, what it takes is making it a priority.


But here we are indeed.

Now Swift is only one example of this, it's a current trend, and of course these systems do claim that they provide benefits that are worth the wait. From optimizations to static type-checking with type-inference, so that "once it compiles, it works". This is deemed to be (a) 100% worthwhile despite the fact that there is no scientific evidence backing up these claims (a paper which claimed that it had the evidence was just shredded at this year's OOPSLA) and (b) essentially cost-free. But of course it isn't cost free:

So when everyone zigs, I zag, it's my contrarian nature. Where Swift's message was, essentially "there is too much Smalltalk in Objective-C", my contention is that there is too little Smalltalk in Objective-C (and also that there is too little "Objective" in Smalltalk, but that's a different topic).

Smalltalk was perfectly interactive in its own environment on high end late 70s and early 80s hardware. With today's monsters of computation, there is no good reason, or excuse for that matter, to not be interactive even when taken into the slightly more demanding Unix/macOS/iOS development world. That doesn't mean there aren't loads of reasons, they're just not any good.

So Objective-Smalltalk will be fast, it will be live or near-live at all times, and it will have instant builds. This isn't going to be rocket science, mostly, the ingredients are as follows:

  1. An interpreter
  2. Late binding
  3. Separate compilation
  4. A fast and simple native compiler
Let's look at these in detail.

An interpreter

The basic implementation of Objective-Smalltalk is an AST-walking interpreter. No JIT, not even a simple bytecode interpreter. Which is about as pessimal as possible, but our machines are so incredibly fast, and a lot of our tasks simple enough or computational steering enough that it actually does a decent enough job for many of those tasks. (For more on this dynamic, see The Death of Optimizing Compilers by Daniel J. Bernstein)

And because it is just an interpreter, it has no problems doing its thing on iOS:

(Yes, this is in the simulator, but it works the same on an actual device)

Late Binding

Late binding nicely decouples the parts of our software. This means that the compiler has very little information about what happens and can't help a lot in terms of optimization or checking, something that always drove the compiler folks a little nuts ("but we want to help and there's so much we could do"). It enables strong modularity and separate compilation. Objective-Smalltalk is as late-bound in its messaging as Objective-C or Smalltalk are, but goes beyond them by also late-binding identifiers, storage and dataflow with Polymorphic Identifiers (ACM, pdf), Storage Combinators (ACM, pdf) and Polymorphic Write Streams (ACM, pdf).

Allowing this level of flexibility while still not requiring a Graal-level Helden-JIT to burn away all the abstractions at runtime will require careful design of the meta-level boundaries, but I think the technically desirable boundaries align very well with the conceptually desirable boundaries: use meta-level facilities to define the language you want to program in, then write your program.

It's not making these boundaries clear and freely mixing meta-level and base-level programming that gets us in not just conceptual trouble, but also into the kinds of technical trouble that the Heldencompilers and Helden-JITs have to bail us out of.

Separate Compilation

When you have good module boundaries, you can get separate compilation, meaning a change in file (or other code-containing entity if you don't like files) does not require changes to other files. Smalltalk had this. Unix-style C programming had this, and the concept of binary libraries (with the generalization to frameworks on macOS etc.). For some reason, this has taken more and more of a back-seat in macOS and iOS development, with full source inclusion and full builds becoming the norm in the community (see CocoaPods) and for a long time being enforced by Apple by not allowing user-define dynamic libraries on iOS.

While Swift allows separate compilation, this can have such severe negative effects on both performance and compile times that compiling everything on any change has become a "best practice". In fact, we now have a build option "whole module optimization with optimizations turned off" for debugging. I kid you not.

Objective-Smalltalk is designed to enable "Framework-oriented-programming", so separate compilation is and will remain a top priority.

A fast and simple native compiler

However, even with an interpreter for interactive adjustments, separate compilation due to good modularity and late binding, you sometimes want to do a full build, or need to rebuild a large part of the codebase.

Even that shouldn't take forever, and in fact it doesn't need to. I am totally with Jonathan Blow on this subject when he says that compiling a medium size project shouldn't really more than a second or so.

My current approach for getting there is using TinyCC's backend as the starting point of the backend for Objective-Smalltalk. After all, the semantics are (mostly) Objective-C and Objective-C's semantics are just C. What I really like about tcc is that it goes so brutally directly to outputting CPU opcode as binary bytes.


static void gcall_or_jmp(int is_jmp)
{
    int r;
    if ((vtop->r & (VT_VALMASK | VT_LVAL)) == VT_CONST &&
	((vtop->r & VT_SYM) && (vtop->c.i-4) == (int)(vtop->c.i-4))) {
        /* constant symbolic case -> simple relocation */
        greloca(cur_text_section, vtop->sym, ind + 1, R_X86_64_PLT32, (int)(vtop->c.i-4));
        oad(0xe8 + is_jmp, 0); /* call/jmp im */
    } else {
        /* otherwise, indirect call */
        r = TREG_R11;
        load(r, vtop);
        o(0x41); /* REX */
        o(0xff); /* call/jmp *r */
        o(0xd0 + REG_VALUE(r) + (is_jmp << 4));
    }
}

No layers of malloc()ed intermediate representations here! This aligns very nicely with the streaming/messaging approach to high-performance I've taken elsewhere with Polymorphic Write Streams (see above), so I am pretty confident I can make this (a) work and (b) simple/elegant while keeping it (c) fast.

How fast? I obviously don't know yet, but tcc is a fantastic starting point. The following is the current (=wrong) ObjectiveTcc code to drive tcc to build a function that sends a single message:


-(void)generateMessageSendTestFunctionWithName:(char*)name
{
    SEL flagMsg=@selector(setMsgFlag);
    [self functionOnlyWithName:name returnType:VT_INT argTypes:"" body:^{
        [self pushFunctionPointer:objc_msgSend];
        [self pushObject:self];
        [self pushPointer:flagMsg];
        [self call:2];
    }];
}

How often can I do this in one second? On my 2018 high spec but 13" MBP: 300,000 times. Including in-memory linking (though not much of that happening in this example), not including Mach-O generation as that's not implemented yet and writing the whole shebang to disk. I don't anticipate either of these taking appreciably additional time.

If we consider this 2 "lines" of code, one for the function/method header and one for the message, then we can generate binary for 600KLOC/s. So having a medium size program compile and link in about a second or so seems eminently doable, even if I manage to slow the raw Tcc performance down by about an order of magnitude.

(For comparison: the Swift code base that motivated the Rome caching system for Carthage was clocking in at around 60 lines per second with the then Swift compiler. So even with an anticipated order of magnitude slowdown we'd still be 1000x faster. 1000x is good enough, it's the difference between 3 seconds and an hour.)

What's the downside? Tcc doesn't do a lot of optimization. But that's OK as (a) the sorts of optimizations C compilers and backends like LLVM do aren't much use for highly polymorphic and late-bound code and (b) the basics get you around 80% of the way (c) most code doesn't need that much optimization (see above) and (d) machines have become really fast.

And it helps that we aren't doing crazy things like initially allocating function-local variables on the heap or doing function argument copying via vtables that require require leaning on the optimizer to get adequate performance (as in: not 100x slower..).

Defense in Depth

While any of these techniques might be adequate some of the time, it's the combination that I think will make the Objective-Smalltalk tooling a refreshing, pleasant and highly productive alternative to existing toolchains, because it will be reliably fast under all circumstances.

And it doesn't really take (much) rocket science, just a willingness to make this aspect a priority.