Denny C. Dai

Denny C. Dai


16 posts

iOS bitcode

how to build a bitcode enabled library

integer overflow in llvm toolchain

unsigned 32bit usage in llvm source code

any static lib larger than 4GB will fail

http://stackoverflow.com/questions/36345266/xcodebuild-linker-assertion-failure

update back to this stack overflow
update back to Apple for the issue

how we solved it while doing bitcode

Profile

Hi, my name is Denny. I am a Software Engineer at Facebook. Previously I worked as a Senior Engineer at Nokia HERE Maps in Vancouver, Canada. This site is a repository of my personal projects and practices. You can find me at dennycd@me.com

iOS symbol visibility control

how to shrink your SDK binary size

Apps

Following is a list of iOS projects I've done either independently or worked on in a previous job.

HERE for iOS (iPhone), 2013 ~ 2015

Nokia HERE
https://itunes.apple.com/app/id955837609


HERE Map for iOS (launched in 2015 Mar). I worked as a Nokia HERE Engineer on the iOS platform SDK team supporting the development and launch of the app.



VanBus (iPhone), 2013

Indie Project
https://itunes.apple.com/app/id642620212


An iPhone app that helps you find out when your next bus is coming in real time. Enter a route or stop number, and get updates on departure, delay and cancels. You can also search for available bus routes nearby and discover the nearest stops to go to.



SmallGo (iPad), 2013

Indie Project
https://itunes.apple.com/app/id568586961


SmallGo is a light-weighted Chinese Go game for casual mobile players. It features a mobile-side game AI that competes with the player at various difficulty levels. The app support both English and Chinese.



WhereWars! (iPhone/iPad), 2011 ~ 2012

Btwxt Games Inc.
website demo


A multiplayer location-based real-time strategy game for iOS platform. I am the Technical Director of the project at Btwxt Games, responsible for the development of iOS game app and the LBS game engine.



Hipster Holiday (iPhone/iPad), 2010

iOS Contractor Work
app page


An interactive hipster quiz app for 2010 Christmas holiday. I am iOS contractor on the project



iConquer (iPhone), 2009

PhD Intern Project, MITACS Accelerate, Vancouver, Canada
paper demo


A location-based game prototype. In iConquer, players can move within a city map using real geo-location and claim territory blocks by carrying their iPhone and drop virtual bots that act on behave of the players. I am the PhD intern student working on the prototype.


AlgorithmBox

AlgorithmBox is an algorithm development toolkit for solving discrete optimization problems. It provides a framework for implementing metaheuristic algorithms in javascript and an empirical experiment library for testing the algorithm against a number of standard optimization problems. It can be installed as a Node.js module via

npm install algorithmbox  

How to Use

With algorithmbox, you can write a few lines of javascript code to implement a local search algorithm and run it against problems such as TSP and SAT. AlgorithmBox defined a number of basic stochastic local search algorithms including

It also provides spec for the following optimization problems

  • Travelling Sales Problem (TSP)
  • Satisfiability Problem (SAT)

To implement a hill climbing algorithm for solving TSP, do the following

//base algorithm definition of hill climbing
var IIA = require('algorithmbox').IIA;  
var defineClass = require('algorithmbox').defineClass;

//extend the framework-provided IIA definition
var MyIIA = defineClass({  
    name : "MyIIA",
    extend : IIA, 
    methods : {

        //given a candidate solution, return a set of neighborhood
        //solutions that can be reached by 1-point mutation
        'neighbors' : function neighbors(candidate) {

        }
    }
});

To load a TSP problem instance from a file such as tsplib, do

var TSP = require('algorithmbox').TSP;

//load tsp instance from file
var raw = fs.readFileSync('tsplib/bayg29.xml');

//parse data and create a TSP instance 
var instance = new TSP(TSP.parseData(raw));  

Now run the algorithm against the problem instance

//create a IIA algorithm with predefined terminate condition
var algs = new MyIIA(instance, {  
    'terminate_ls_steps' : 1000  //stop if maximum search steps reached
});

//run the algorithm and monitor progress
algs.run(function(step){  
    console.log("step %d. best found solution: [%s]", step, algs.best_sol);
    if(algs.lo_trap)
        console.log("trapped");  //algorithm trapped in local optima
});        

Experiment and Analysis

AlgorithmBox provides a simple framework for experimenting with different problem instances and algorithm parameter configurations . To define an experiment

var Experiment = require('algorithmbox').Experiment;

var config = {  
    //test against TSP problem class
    "tsp": { 
        //run each algorithm against each TSP instance loaded from a file
        "instances" : ["bayg29.xml", "br17.xml"],   

        "algorithms": {
            //setting for a user-defined Simulated Annealing algorithm 
            "tsp_sa": [ 
                {
                    "boltzmanconst": 0.05,
                    "coolingscheme": "geometric"
                }, {
                    "boltzmanconst": 0.005,
                    "coolingscheme": "geometric"
                }, {
                    "boltzmanconst": 0.001,
                    "coolingscheme": "geometric"
                }, 
            ]
            //settings for a user-defined hill climbing algorithm
            "tsp_iia": []
        },

        //total number of independent runs (with random restart)
        "runs": 100,

        //terminate condition for each run
        "max_ls_steps" : 5000
    }
};

To run the experiment and output the raw data result to a folder:

var session = new Experiment(config, "default.box");  
session.run();  

To analyze the experimental result, use the Analyzer to load the experiment raw data

var Analyzer = require('algorithm').Analyzer;

//load runtime quality distribution result for a specific algorithm runed against a specific problem instance
var rqds = analyzer.get_runtime_quality("sat", "uf20-01.cnf", "gsat_iia", {"terminate_ls_steps" : 30});  
var rqds2 = analyzer.get_runtime_quality("sat", "uf20-01.cnf", "gsat_iia", {"terminate_ls_steps" : 10});  
var rsd = analyzer.get_runtime_solvability('sat', "uf20-01.cnf", "gsat_iia", {}, 85);  
rsd = analyzer.get_runtime_solvability('tsp', "bayg29.xml", "tsp_iia", {}, 1800);

AlgorithmBox provides the following experimental analysis matrix

  • Runtime Quality Distribution showing how solution quality changes over local search steps
  • Runtime Solvability Distribution showing the probability of reaching a solution quality over local search steps
  • Problem Solution Quality shows the average solution of the algorithm across mutlitple problem instances over a number of indepedent runs

For further details, please look into the test case examples.

Visualization and Ploting

A sample visualization is provided (test/test_visualization.js) that demonstrate how to use Socket.IO and D3 to visualize the runtime quality distribution of a typical experiment. In the test folder, do

nodeunit test_visualization.js  

In the browser, open

localhost:8888  

and you would obtain the runtime quality distribution showing how solution quality (Y Axis for minimization problem) improves over runtime (X axis as local search steps)



Source Code and RoadMap

https://github.com/dennycd/algorithmbox
AlgorithmBox is still a new concept under developement. Contributors are welcomed.

simple-cls

a simple class system for node.js that adds a number of object-oriented features to the basic javascript language, including

  • convinient class definition with inheritance
  • abstract class a.k.a. interface support
  • runtime introspection with dynamic type checking

The design goal is to provide a clean and easily understandable class system while minimizing overhead and avoid poluting the javascript built-in objects. It is inspired and built upon the defineClass from JavaScript The Definitive Guide.

Usage

Install the package "simple-cls"

npm install simple-cls  

To define a class, do the following

var cls = require('simple-cls')

var MyClass = cls.defineClass({  
    //optional class name 
    name : "MyClass",
    //optional super class, default is Object
    extend : BaseClass,
    //constructor code
    construct : function(msg){
        this.msg = msg;
    }, 
    //instance methods
    methods: {  
        foo: function() {
            console.log("foo");
        }
    },
    //instance variables
    variables: {
        bar : 1,
        msg : null
    },
    // class level variables or methods
    statics : {

    }
});

To instantiate an object and start using it

var obj = new MyClass("hello");  
obj.foo();  
console.log(obj.bar);  

Concept



in simple-cls, the class system is built upon a chain of triple objects, namely the Prototype, Constructor and Class. As the diagram shows, instantiating a new js object will establish a relationship from the bottom up, starting at the object instance. Using javascript's built-in function we can obtain the prototype of that object.

assert.ok(Object.getPrototypeOf(obj) === MyClass.prototype);)  

The prototype object itself is an object instance of the superclass of MyClass. If no superclass is given, it is defaulted to Object. MyClass is an alias of the Constructor function for obj

assert.ok(obj.constructor === MyClass)  

The Class object contains runtime information about the obj class and can be obtained via __class on the constructor or .getClass() methods

assert.ok(obj.constructor.__class === obj.getClass())  

To check if a js object is an instance of a class, or an instance of a subclass of some super classes

test.ok(obj.getClass().isKindOfClass('MyClass'));  
test.ok(obj.getClass().isKindOfClass('BaseClass'));  
test.ok(obj.getClass().isKindOfClass(MyClass.__class));  
test.ok(obj.getClass().isKindOfClass(BaseClass.__class));  

To look at all the methods callable from the obj, including methods defined on the super class

console.log(obj.getClass().getMethods());  

For details, please look at the unit test examples.

Source Code

https://github.com/dennycd/node-cls

node-tralic

A node.js module for converting latex source to javascript json. It is a wrapper based on the following c library

To install the package in npm

npm install tralics  

To analyze a latex file

var tralic = require('tralics');  
var util = require('util');

tralic.analyze("hello.tex", function(doc){  
    console.log("DOC " + util.inspect(doc));
});

Source Code

https://github.com/dennycd/node-tralic

lucene.js

A Javascript Port of Apache Lucene Core. Lucene.js is a javascript implementation of the popular apache lucene search engine core. you can use it as

  • a server-side javascript module running on Node.js
  • a js library run directly in the client-side browser

Library features including

  • framework API conforming to the latest apache lucene core spec
  • pure javascript-based implementation with optional C++ node.js module addon
  • integrated networking module
  • indexing DB with efficient and scalable data structure format

Source code

https://github.com/dennycd/lucene.js

libgeocached

A fast in-memory geospatial index and query library in C++. The library supports the following

  • indexing of arbitray object types with geolocation tag via C++ template
  • efficient geohash-based spatial partitioning and search tree implementation for geospatial query
  • optional persistency support for NoSQL library including Redis and MongoDB (in-progress)
  • cross-platform availability incluing MacOSX, iOS, GNU Linux, Node.js and Windows

Usage

To create a new geocache matrix, do

#include <matrix.hpp>

libgeocached::Matrix<DataObject> matrix; //DataObject can be any type  

To add an object into the matrix and associate it with an id and location tag:

//data insertion
ObjectID id1 = ObjectIDNew();  
DataObject obj("dummy");  
GCLocation location =  GCLocationMake(23.23234, -123.34324);  
matrix.insert(id1, obj, location);  

To query for all objects within a circular geographical area

#include <vector>
...
//define a circle area with center lat/lng and 1000 meter radius
GCCircle circle = GCCircleMake(GCLocationMake(23.23234, -123.34324), 1000);  
std::vector<DataObject> objs;

//circular query
matrix.objs_in_circle(circle, objs);

for(DataObject& obj : objs)  
    cout << obj << endl;

Internal Implementation

libgeocached uses an efficient search tree implementation called GCTree for hierarchical partitioning of geographical space and object indexing. Each tree node represents a rectangular geo cell with bounding latitude (north,south) and longitude (west,east) edges. It uses a binary representation of the geohash values for both lat and lng. For example, a 15bit precision binary geohash

latitude:  0b101000010000101  
longitude: 0b001010000100101

represents a rectangle bounding box of the following edge values

lat_south:    23.2305908203125  
lat_north:    23.236083984375  
lng_west:    -123.343505859375  
lng_east:    -123.33251953125  

Each internal tree node has a branching degree of 4, with each child representing adding an additional lowest bit to its latitude and longitude values

lat lng  
0   0    south half along latitude, west half along longitude  
0   1    south half along latitude, east half along longitude  
1   0    north half along latitude, west half along longitude  
1   1    north half along latitude, east half along longitude  

By going down 1 tree level, the geo cell is partitioned into four sub regions by halfing at the centre line along both latitude and longitude directions. Internal node at tree level k represents a geo rectangle having k bit precision (assuming 0 bit at root node). The leaf node of the tree has the highest bit precision and therefore corresponding to the smallest geo rectangle. Reference to the objects are stored at the leaf nodes.

Runtime Complexity

For a fixed maximum bit representation, the height of the GCTree is bounded by the number of bits K. Therefore inserting an object into the tree is bounded by O(K) . Deletion via geolocaiton tag also requires finding the leaf node containing the object which is O(K).

A spatial query on the gctree resembles that of a R-tree operation by first locating the minimum bounding rectangle cell encompassing the query region, and then recursively traverse down the sub regions and collect all objects fall within the query area.

Performance

More performance evaluation matrix to come for the next milestone release

Version

Current: 0.0.1

Build and Install

platform specific build scripts and projects are available under build folders

References

Source Code

https://github.com/dennycd/libgeocached