Caching with NSCache, or, The most underrated Objective-C Class

“There are only two hard things in Computer Science: cache invalidation and naming things.” —Phil Karlton

There are four things you need to know about NSCache. The first, and most important: NSCache exists. I recently wrote a cache object in Objective-C, this was a mistake. I Google’d “objective-c cache class”:

NSCache

Unhelpful Google results for “objective-c cache class”.

Top results looked uninteresting and I was feeling saucy; so I implemented one from scratch. I will be happy if this post serves no other purpose than to prevent you from making the same mistake. Now that you know the most important thing about NSCache, here are three more things you should know (especially if you still want to implement your own cache, which I recommend as an exercise). [1]

  1. Apple does not publish NSCache’s auto-removal policy, it is subject to change. I would guess it’s caching algorithm is something like LRU (which is what GNUStep’s implementation uses). [3]
  2. NSCache is thread-safe, no need to @synchronize access.
  3. NSCache does not copy the objects put into it, it keeps (and retains in non-ARC) pointers to cached objects. [1]

So put down that thread-unsafe NSMutableDictionary, pick up your NSCache, and stop reinventing the wheel. Or, at least know that it exists before you go making improvements.

Sources & Further Reading:

[0] Phil Karlton (Who deserves a Wikipedia page but that’s another story)
[1] Apple’s Documentation on the NSCache Object
[
2] http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
[3] GNUStep’s implementation of NSCache – NSCache.m

It’s programming from here on out

There comes that point in every project where the “hard” part has been solved. Where the learning curve has been topped and one can start getting into the flow. The hacker equivalent to “smooth sailing from here on out”:

“It’s programming from here on out.”

Happy hacking.

Graph Visualization with GraphViz

I have a few idaes for startups with a graph-like structure and found myself exploring the topic of graph visualization. I decided to see if I could generate some graphs containing hundreds of thousands of edges. Tools of choice: bash, python, and GraphViz1.

RandomSubset(p)

Using my template I first made a graph of a random subset of (p * 100)% of the 2-tuples in the cartesian product between the first X integers:

[(a, b) for a in range(X) for b in range(X) if random() < p]

Here’s the middle of the graph for p=0.02:

Graph of random subset (2%) of the possible pairings of the first 10,000 numbers.

CommonFactors(x, y)

Next, I decided to see what the graph of integers < X that have more than Y factors in common.

[(a, b) for a in range(X) for b in range(X) if len(common_factors(a,b)) > Y]

 

Here’s the graph for x=10 000, y=5:

This is a graph visualization with X=10 000 and Y=5
A focus on the heavily linked part of for x = 10 000, y = 5

A GraphViz example of integers with common factors -- point shape used for nodes

Here’s one for x=10 000, y=30

x=10 000 y=30

I found them all to be quite beautiful.

The Code

If you want to check out the source code, here’s the github: https://github.com/stephenbalaban/biggraphs.

Note: The first image is a section of an earlier iteration of the CommonFactors graph.

[1] GraphViz project: http://graphviz.org – I used the point shape for the nodes here’s the part of the code that describes my graph style:

graph gengraph {
        graph [bgcolor="#FFFFFF", outputorder="edgesfirst", dpi=1000];
        node [width=0.0008, fixedsize=true, shape=point, color="#00000099"];
        edge [penwidth=0.1, color="#00000099"]graph [bgcolor="#FFFFFF", outputorder="edgesfirst", dpi=1000];
        a -- b;
        b -- a;
        a -- c;
        c -- a;
        a -- d;
        b -- d;
        c -- d;
}

Augmented Reality AR Glasses App – Saving Face

“Saving Face” is an augmented reality glasses app that leverages social networks, facial recognition algorithms and cloud infrastructure to automagically recognize and remember people. It merges linked data from social networks and live augmented reality to provide a layer of data over your social interaction.

This was a super-quick & dirty hack that we threw together in 30 hours at angelhack, please excuse any outrageous headgear or naughty errors!

All things being equal, this is the future of computing. Coming soon to a social interaction near you.

facebook IPO $100 billion valuation and the cost of a personal space program

Here’s the math:

Facebook IPO: $100 billion valuation
Mark Zuckerberg’s ownership: 24% [0]
Value: 24 billion USD

Cost of the Mercury Project (to put a man into orbit around the earth)
Total: $392.6 million (1969 dollars) [1]

Present day cost of Mercury Project: $2.457 billion USD [2]

By selling 10% of his personal shares, he could finance his own personal space program.

Mercury Space Program, the Mercury Capsule creating a parabolic arc over the ocean.

[0] http://en.wikipedia.org/wiki/Template:Facebook_navbox
[1] http://en.wikipedia.org/wiki/Project_Mercury
[2] www.wolframalpha.com/input/?i=392.6+million+1969+dollars

Compiling vim with python support on Arch Linux; or, just using gvim

I was looking forward to using ConqueTerm on vim but was confronted with the following error:

Conque ERROR: Python interface cannot be loaded

Your ersion of Vim appears to be installed without the Python interface…

Alas, the eternal struggle between convenience & elegance. Because I should be doing more important things than blogging, I slapped a big old piece of duct-tape on this problem:


sudo pacman -Ss gvim

Despite the monstrous dependencies (ruby, gtk2, …):


$ pacman -Qi gvim

称   : gvim
版本   : 7.3.353-1
URL地址 : http://www.vim.org
软件许可 : custom:vim
软件组  : 无
提供   : vim=7.3.353-1
依赖于  : vim-runtime=7.3.353-1 gpm ruby libxt desktop-file-utils gtk2 lua
可选依赖 : 无
要求被  : 无
冲突与  : vim
取代   : 无
安装后大小: 2704.00 K
打包者  : Eric Belanger
架构   : i686
编译日期 : 2011年11月08日 星期二 23时05分50秒
安装日期 : 2011年11月22日 星期二 12时54分42秒
安装原因 : 单独指定安装
安装脚本 : 是
描述   : Vi Improved, a highly configurable, improved version of the vi text editor (with advanced features, such as a GUI)

I figured it would be better to spend my time elsewhere. So I simply installed gvim and it worked like a charm.

Why Code Hero will save the American economy, and so should you

You are going to die.

Few try to change the world during their brief tenure, fewer still try to change it for the better. Few step into the arena and spend themselves for a worthy cause. From the moment you come kicking and screaming into this world, you’re dying. By the time you’re “educated” with a college degree, you’re already 1/4 of the way out the door. What side of human progress are you?

It’s inspiring to know people like Alex Peake. We’re all capable of being catalysts of change in our environments; what have you done to change the world this month?

we are going to die

We are going to die, and that makes us the lucky ones. Most people are never going to die because they are never going to be born. The potential people who could have been here in my place but who will in fact never see the light of day outnumber the sand grains of Arabia. Certainly those unborn ghosts include greater poets than Keats, scientists greater than Newton. We know this because the set of possible people allowed by our DNA so massively exceeds the set of actual people. In the teeth of these stupefying odds it is you and I, in our ordinariness, that are here. We privileged few, who won the lottery of birth against all odds, how dare we whine at our inevitable return to that prior state, from which the vast majority have never stirred.
—Richard Dawkins

Bjarne Stroustrup Talk at UMich Notes

Bjarne Stroustrop
2011年 11月 09日 星期三 17:18:36 EST
-------------------------------------------------------------------------------

Multi-paradigm is not good enough
Light-weight abstraction
    - software infrastructure
    - resource constrained

No one size fits all
    - 1st to market
    - If program fails, people die
    - 50% overhead implies the need for another $50M server farm

What we want
-------------------------------------------------------------------------------
Easy to understand

- Modularity
- No resource leaks
- Thread safe
- Efficient
- Portable

Ghastly style

ugly -> cin>>val

Bad style is the #1 problem in real-world C++ code
    - bad code *BREEDS* more bad code
    - Many are self-taught
        - advice from decades old books/novices

Mars lander
-------------------------------------------------------------------------------

Using *UNITS*

Speed sp1 = 100m / 9.8s // very fast for a human
...
Acell acc 
...

Using operator ""s, operator ""m, operator ""kg -- Elegant!

Keep interfaces strongly typed
    - avoid very general types
        - int, double, ...
        - Object....

Checking of trivial types finds trivial errors

void f(const char* p) {
    f = fopen(p, "r");
        ....
    fclose(f);
}

(*The number of bugs you have in your problem is proportional to the amount and
complexity of the code you have got.*)

RAII - resource acquisition is initialization

~File_handle() { fclose(p) } // destructor

RAII lowers the time you use resources compared to other strategy
    - manually
    - finalizer
    - garbage collection, etc...

Not all resources are scoped

Most uses of scoped resource allocation is no exception-proof

std::shared_ptr releases its object at when the last shared_ptr is destroyed
std::unique-ptr is the same

Gadget g {n}; // No naked 'new' s!

-------------------------------------------------------------------------------
Range-checks on containers, no more overflows

Resource handles and pointers "smart pointers" address most memory leak
problems
-------------------------------------------------------------------------------
Use data types that integrate this into their behavior:
    std::vector, std::ostreamm, std::thread, ...

Moving large objects out of a function

Move the Matrix out
    "steal the representation"

Use the Move Constructor in X11
    class Matrix {
        //
        ..
    }

New X11 
Not array -- because array is a chunk of memory

- no naked pointers
- no naked new or delete
    - keep arrays out of interfaces (prefer containers)
    - pointers are implementation-level details
    - use unique_ptr and shared_pointer
- return objects "by-value" (using move rather than copy)


Vector vs List
To answer this---
Know:
    - complexity theory
    - data structs.
    - machine architecture
     - *ran out of memory before list's advantage could show itself*
- Amount of memory used differ dramatically
- Memory access is relatively slow
- Implications

We *NEVER* hit the asymptote!

* Compactness
* Generic Code

Algorithms vs."Code"

Need to get to a more algorithmic version of code
-> gather example

A.K.A. C++ is becoming more like python

Low-level != efficient
-------------------------------------------------------------------------------

Don't lower your level of abstraction without good reason
Low-level implies
    more code
    more bugs
    harder to understand and maintain

Inheritance
    - When the domain concepts are hierarchical
    - When there is a need for run-time selection among hierarchically ordered
      alternatives

Type-Safe Concurrency

auto --> gets type of initializer

async() - pass arguments and return result
auto res1 = async(f, some_fec);
cout << res1.get();
get return value when you want it

-------------------------------------------------------------------------------
tldr;
C++ Style
Practice type-rich programming
    - focus on interfaces
    - simple classes are cheap - use lots
    - avoid over-general interfaces
Use compact data structures
    - by default, use std;:vector
Have a general strategy for error handling
    - By default, us exceptions and RAII
Prefer algorithms to "random code"
Rely on type-safe concurrency
Build and use libraries
    - By default, start with the ISO C++ standard library

Q&A
- What languages do you feel have features you would like to see in C++?
- Threads & Concurrency now in ISO std C++ 
    - shipped in MS/GNU/CLANG compilers

"Not a science fiction tour -- all shipped"