Oleg Andreev
Month
“The name, if you’re wondering, comes from the simplest sequence of operations which will thoroughly mix the bits of a value - "x *= m; x = rotate_left(x,r);” - multiply and rotate. Repeat that about 15 times using ‘good’ values of m and r, and x will end up pseudo-randomized"
Austin Appleby.
HFS+ also has a few specific optimizations. When a file is opened on an HFS+ volume, the following conditions are tested:
— The file is less than 20 MB in size
— The file is not already busy
— The file is not read only
— The file is fragmented (the eighth extent descriptor in its extend record has a non-zero block count)
— The system uptime is at least 3 minutes
If all the above are satisfied, the file is relocated (de-fragmented) - on-the-fly.
”—What Is Mac OS X?, Mac OS X Filesystems (Amit Singh)Thanks to gotsyk for the link.
Thanks to julik for the link.
The encoding scheme is required to
— Be human readable and machine readable.
— Be compact. Humans have difficulty in manipulating long strings of arbitrary symbols.
— Be error resistant. Entering the symbols must not require keyboarding gymnastics.
— Be pronounceable. Humans should be able to accurately transmit the symbols to other humans using a telephone.
The parser enables you to write BNF-like rules directly in JavaScript without need to compile the file (like with Ragel, YACC, Bison, ANTLR etc.)
The grammar is a JS function with 11 arguments (9 rules and 3 hooks). Each rule gets two arguments: text (string) and state (arbitrary value) and returns a tuple of new text and new state (or null if rule was not matched). Parser walks character by character from left to right. text is always a tail of the initial text. Generally, text is empty string when parser finishes.
All(rule1, rule2, …) — a sequence of rules. Example: All(Char(“[”), list, Char(“]”)) defines a JS array.
Any(rule1, rule2, …) — “OR” rule for any number of rules. Example: JSONValue = Any(StringRule, ObjectRule, ArrayRule, …)
Char(alphabet) — character matching rule. Example: digit = Char(“0123456789”)
NotChar(alphabet) — inverse of Char(). Any character — NotChar(“”).
Optional(rule) — tries to match rule and skips it if not matched. Example: optSpace = Optional(Char(“ \t\r\n”))
EOF — matches the end of the text. Fails if text != “”.
Terminator — terminates parser. That is, always returns empty text.
Y — Y-combinator for defining recursive rules. Example: X = Y(function(x) { return abc(x) } ), where x is equal to X. Google for more info on Y-combinator.
Hooks enable you to actually build some structures using your grammars. Every hook returns a new state value to use in further rules. You should avoid mutable state values because some rules may be thrown away if not matched later (remember: this is a recursive parser!). For example, use array.concat([value]) instead of array.push(value).
Capture(rule, function(buffer, state1){ return state2 }) — captures raw string buffer to store in the state2.
Before(rule, function(state1){ return state2 }) — creates a new state for the rule (e.g. creates empty array for array syntax).
After(rule, function(beforeState, afterState){ return newState }) — creates a new state after successful match. You can put nested values to the container if beforeState is a container before rule parsing, afterState is a nested value (after rule match) and newState is a new container with this value.
See usage examples in JSONGrammar.js
See the parser source code in Parser.js
How to use Natural Order
Drop Natural Order into the System Folder and Restart your Mac.
”—NaturalOrderSort.orgA Cool And Practical Alternative To Traditional Hash Tables
More Robust Hashing: Cuckoo Hashing with a Stash
Recent advances in the theoretical literature have proposed interesting modifications to traditional hash tables. The authors of these papers propose hash tables which
a) have a guaranteed constant time for a lookup
b) have amortized constant time for an insertion
c) require table size only slightly larger than the space for the elements
Previous hash table technologies have offered at most two of these three.
(Thanks to Julik for inspiring to think on the subject.)
In Io, JavaScript and Python there’s a model of “hash-table” objects. The object contains some slots, which you access and then decide what to do with them. If the slot appears to be a function, you can call it. In JS there’s a bit of magic: interpreter knows where the function just came from, so it can specify reasonable “this” pointer for function call. In Io there’s less smart decision: upon slot access interpreter checks “activatable” property of the object (not the slot entry, but the object this slot refers to!) and activates the object if it happens to be a method. However, in Io x := y is being a message setSlot(‘x’, y), so that you can hook in.
On the other hand, Ruby has a much stronger notion of message passing: you never ever can modify inner object data (that is, @ivars) without message send. The most simple @foo update happens through the accessor method called foo=.
However, from the implementation point of view, Ruby has two kinds of hash tables per object: method table and ivars table.
Implementation is created under time and knowledge constraints. Therefore, it is full of bugs, and it becomes obsolete as soon as our knowledge evolves. What is important in technology: the idea and context behind each decision.
MyApp := Object clone do(
Foo := Object clone do(
bar := method(Bar) # Bar is not accessible from here!
)
Bar := Object clone do(
foo := method(Foo) # Foo is not accessible from here!
)
)
How can we improve that? First, lets define MyApp with Module clone rather than Object clone:
MyApp := Object Module clone do(
Foo := Object clone do(
bar := method(Bar)
)
Bar := Object clone do(
foo := method(Foo)
)
)
All we need now is to have all inner objects to have MyApp in the list of prototypes. Therefore, lets override Object slot to refer to MyApp rather than the standard Object:
Module := Object clone do(
Object := method(self)
)
See Module.io on GitHub.Yesterday I have rewritten 3600 LOC codebase in ActionScript as if there were “message eating” null in the core and the standard libraries (please see A Generalized Null Object Pattern by Nevin Pratt). I got a diff with just 100 lines removed and 180 lines updated. It is at most 7% code reduction.
It seems that “message eating” null neither produces considerably more elegant code, nor considerably more brittle code (in all cases ignoring null value is correct).
In sense of VM implementation, it might be easier to implement a classical “exception raising” null and use custom Null Pattern classes where appropriate.
Good software framework saves much more time providing explicit knowledge where to put things in, rather then providing syntactic steaks and strippers.
iovm idea: “activatable” should be a slot property rather than value property. This allows to pass methods around and access them directly by slot name in all the contexts. Current implementation makes you to use getSlot(slotName) syntax to avoid activation.
Excellent write up about “message eating” Nil.
There’s no “srand” function in AS3. That is you cannot seed random number generator.
And when you get the very same results each time swf is loaded you find this:
However, if you need true randomness in an event-driven application, you can do this:
setInterval(Math.random, 10)
Flash Player will run Math.random() in background producing different random values at different points of time.
In a regular priority queue entry with priority N is taken before all the entries with priority M (given N > M).
Sometimes, however, 3-priority entry should not beat one hundred of 1-priority items. It seems natural to introduce a double-linked list of weighted nodes, where newly inserted node can come in front of a limited number of nodes with a total weight less then a weight of a new node.
Illustration. Given a stream of nodes with weights:
[1a, 2, 1b, 3, 1c, 1d, 4, 1e]
weighted queue intermediate states would be:
[1a]
[2, 1a]
[2, 1a, 1b]
[2, 3, 1a, 1b]
[2, 3, 1a, 1b, 1c]
[2, 3, 1a, 1b, 1c, 1d]
[2, 3, 1a, 4, 1b, 1c, 1d]
[2, 3, 1a, 4, 1b, 1c, 1d, 1e]
In such queue priority “N” means skipping N items of priority 1.
Observation: office becomes nicer when everybody leaves :-)
// I dedicate all this code, all my work, to my wife, Darlene, who will // have to support me and our three children and the dog once it gets // released into the public.”—Stack Overflow: What is the best comment in source code you have ever encountered?
Say, you want to keep some auxiliary info inside your git repository: tickets, post-commit/post-receive hooks, wiki pages etc. Storing them inside a folder might not be a good idea: you’d probably want to have same content across all the branches. It is natural to keep such data in a separate branch.
Given that, you can create your “tickets” branch simply by checking out new branch, removing all the code, adding initial files and committing it. This works great until you get bored with the irrelevant history in the tail of the git-log. It is rather easy to disconnect your branch from the old history: just take the latest tree id, create an orphan commit (that is: without parent commits) and reset branch to this commit.
# emit tree id for the latest commit
$ git log -1 --pretty=format:%T
# emit new commit id
$ echo "initial commit" | git commit-tree <tree-id>
# reset current branch to this commit id
$ git reset --hard <commit-id>
Put it in a single bash command:
$ git reset --hard `echo "initial commit" | git commit-tree \`git log -1 --pretty=format:%T\``
Dangling branches are great for keeping meta-data of any sort: .git/config files, tickets, hooks, documentation, tickets.
PS. Since you can store hooks inside repository itself, you can have a self-contained deployment system like Capistrano without any additional tools installed on a server. Hooks can even update themselves on each post-receive hook before actual deployment recipes are run. This allows you to specify all the dependencies in the source repository and even setup them with a single “git push” command. All manual setup you have to do initially is to clone local repository inside .git/hooks folder (yes, inside itself) and check out hooks branch appropriate for your environment. Ain’t that sweet?
Nice article showing efficiency and inefficiency of TraceMonkey. Must read.
FriendFeed stores all entities with all properties in a single table and uses separate tables for specific indexes. After retrieving entities from the index, application reapplies query to fight some data inconsistencies. Eventually, “cleaner” process updates indexes with the actual data. This strategy greatly reduces administration efforts (indexes can be created or update asynchronously) and makes latency 2x lower.
(Thanks Application Error for the link)
DIAGNOSTICS
You don't exist. Go away!
The passwd(5) gecos field couldn't be read
Your parents must have hated you!
The passwd(5) gecos field is longer than a giant static buffer.
Your sysadmin must hate you!
The passwd(5) name field is longer than a giant static buffer.
def movie_events_grouped_by_titles_and_theaters
events = Event.all.inject({}) do |titles, event|
((titles[event.title] ||= {})[event.theater] ||= []) << event
titles
end
end
(my response to the mail list discussion; in russian)
[user]
name = Oleg Andreev
email = oleganza@gmail.com
[apply]
whitespace = strip
[diff]
color = auto
rename = copy
[pager]
color = true
# this one is very cool:
# green means "to be committed"
# red means "not to be committed"
[status]
color = auto
Must read.
Today I have received a letter:
^_^Hello Oleg,
I’m a Io newbie. I was watching some of your sample code on Github (loved funnyFactorial ;-) when I discovered your “learning french” subdir. I’m french and would be pleased to answer / comment / whatever about that language (not so human).
Github offers you a HTTP server for static data at http://yourname.github.com. Publishing is easy: just push content to git@yourname.github.com. (It is two months already, how could I miss!)
$ git rev-list -n 1 HEAD <path/to/folder>
Returns the latest commit, which modified a given path. This is useful to find out whether something has recently changed in the particular folder.
Young hacker looks at the figures: “2 hours for the feature Foo, 4 hours for the feature Bar”. He feels that kind of pressure: “I have to make it! I have to type faster, think faster, test faster.”
This is an awful feeling. So here’s the (possible) solution to this situation: try to think of time as of money you are investing. Tell yourself how much time of your life would you invest into this piece of #$@^ (of course, take into account your rate/salary). Now it looks like you score the feature Foo for just 2 hours: it doesn’t worth 4 hours or more. Spend 10-15 minutes for planning the way to spend that much time and do your best. If some trouble strikes and you’re out of time, just give up. Go to another feature and let this to be discussed on a weekly meeting when there’s time to schedule next iteration.
If the client wants a fixed price for software, you will not have any additional time. In such case - either do a dirty job, or work all the night. You to decide.