tag:blogger.com,1999:blog-32466700762940026682023-06-20T09:09:22.397-04:00shiftpopMarkhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3246670076294002668.post-48208353818707943512022-03-09T00:12:00.001-05:002022-03-09T00:12:15.307-05:00Diana says it's time to go to sleep.<p>Diana says: "Are you blogging again?"</p><p>As soon as a press this button I am!</p>Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com0tag:blogger.com,1999:blog-3246670076294002668.post-49592417290150318762015-01-31T14:11:00.000-05:002015-01-31T14:11:30.698-05:00Blogging Again?Given that the last post on this blog was made in 2008, you might think I had forgotten about it entirely. I haven't forgotten. I want to write again.<br />
<br />
Diana told me about <a href="http://750words.com/">750words.com</a>, and I gave it a try. I've typed out 750+ words every morning for that last 12 days. My joint pains and mental fog have decreased each day! I'm breaking through into a new realm of consciousness! Just kidding, but it has been nice.<br />
<br />
I like the name of this blog, and I like the banner image that I made for it (seven years ago!). The name "shiftpop" sounds like a musical micro-genre, and also like an instruction in a stack-based programming language. In 2008 when I started this blog, I was at the apex of my cellular automata (the banner image) and non-mainstream programming languages (the blog name) phase.<br />
<br />
I'm a bit nostalgic for that era, but I don't expect to write about either of those topics now. I do intend to write about technical issues, but I'm more likely to write about computer graphics and hardware verification.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com0tag:blogger.com,1999:blog-3246670076294002668.post-7931068393230239552008-12-30T10:36:00.002-05:002008-12-30T11:10:07.758-05:00PHP's strtotimeI generally think of PHP as the buck-toothed high-school drop-out sibling of Perl (itself the unbathed cousin of Python and Ruby). But today I discovered the library function <a href="">strtotime</a>, which is a very flexible parser for text expressing a date/time. One cool example is <a href="http://brian.moonspot.net/2008/09/20/strtotime-the-php-date-swiss-army-knife/">a snippet that calculates the current year's Thanksgiving day</a>.<br /><br />The closest Python equivalent to <i>strtotime</i> seems to be <a href="http://labix.org/python-dateutil#head-c0e81a473b647dfa787dc11e8c69557ec2c3ecd2">dateutil.parser.parse</a>, though it's much less flexible from a cursory glance. Of course, if a person is only trying to compute "<i>common moveable Christian feasts that can be deduced from the date of Easter Sunday</i>" they need look no further than the <a href="http://books.google.com/books?id=bqteixWa98wC&pg=PA259&lpg=PA259&dq=mx+date+feasts&source=web&ots=O5Xedzu-e7&sig=GIi7n_oj9PQFLOgqcdKxSIwI6QY&hl=en&sa=X&oi=book_result&resnum=4&ct=result">mx.DateTime.Feasts</a> library (which includes translations into German and French). Weird. And awesome.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com2tag:blogger.com,1999:blog-3246670076294002668.post-7682568176916294392008-12-05T10:35:00.002-05:002008-12-05T11:00:14.515-05:00Not Lazy EnoughIt occurred to me that many performance problems when dealing with large datasets are due to programs not being "lazy enough". My example problem was "ALTER TABLE" statements in a database, which in most implementations will read, modify, and write every row in the table. Because with large tables this is a significant performance hit, we rarely see people doing "dynamic language things" i.e. altering their schemas in application logic.<br /><br />One reason for being non-lazy (some say: strict) is to ensure consistency across your dataset. If exact consistency is not a requirement, object/document stores like CouchDB or AppEngine's datastore can provide inexpensive "ALTER TABLE" behavior. With these systems, outdated/unaltered rows only need to be upgraded/altered when they're fetched from the datastore. Here's a case where deferring the "ALTER TABLE" code allows us to write more flexible/dynamic programs because our data management is lazier.<br /><br />Code can be too lazy though, resulting in bad caching behavior and sometimes huge memory space growth.<br /><br />Any other examples of cases where laziness/demand-driven-evaluation would be a performance win?Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com0tag:blogger.com,1999:blog-3246670076294002668.post-52417157718909017042008-10-10T00:20:00.005-04:002008-10-10T01:30:28.976-04:00Ten Years of Progress"I'm afraid this is very bad. The stones tell me the boar god came from far to the west."<br /><img src="http://www.geocities.com/ericliao12/wise-woman.jpg"/><br /><br />Hello from October 10th 2008. The Dow Jones Industrial Average closed yesterday at <a href="http://finance.yahoo.com/q/hp?s=%5EDJI&a=09&b=8&c=2008&d=09&e=11&f=2008&g=d">8,579</a> which is a little bit under its close of <a href="http://finance.yahoo.com/q/hp?s=%5EDJI&a=02&b=8&c=1998&d=02&e=11&f=1998&g=d">8,643</a> on March 10th 1998.<br /><br />Does this mean that the global economy could have been <i>put on hold</i> ten years ago and life would be just the same today?<br /><i>Probably not.</i> People have to eat.<br /><br />Does it mean that ten years worth of free market profit motive could have been thrown out the window, that executives could have been told to just <i>keep 'er runnin'</i> and life would be just the same as today?<br /><i>Probably not.</i> There have been winners and losers, and markets have adjusted for changing consumer preferences over the decade.<br /><br />I don't know what it means.<br />But it does seem like an appropriate time to ask:<br /><b>"Have we been making <a href="http://en.wikipedia.org/wiki/Progress">progress</a>?"</b><br /><br />I think that the answer is: Yes!<br /><br />Though we may have to scale down our retirement plans, and start buying the less expensive brand of veggie burgers, our Wikipedia Content Index (WCI) just keeps growing:<br /><a href="http://upload.wikimedia.org/wikipedia/commons/6/6f/EnglishWikipediaArticleCountGraphs.png "><img src="http://upload.wikimedia.org/wikipedia/commons/6/6f/EnglishWikipediaArticleCountGraphs.png" width="400"/></a><br /><br />And lest we ignore the importance of emerging global cute funds, think of how far we've come since <a href="http://www.google.com/search2001/search?hl=en&q=lolcats&btnG=Google+Search">1998: a world without lolcats</a>.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com1tag:blogger.com,1999:blog-3246670076294002668.post-68052336197820512082008-09-25T14:14:00.004-04:002008-09-25T15:48:27.248-04:00Compiling x264 with MP4 support on OS XI've been wanting to futz around with the internals of a modern video codec, and since H.264 seems like a pretty happening codec, and the x264 project seems pretty awesome, I downloaded their source and tried compiling it on my Mac. I hit a few roadbumps, so here are instructions for anyone else who wants to compile x264 on OS X:<br /><br /><pre><br />wget http://downloads.sourceforge.net/gpac/gpac-0.4.4.tar.gz<br />open gpac # lazy-man's untar<br />git clone git://git.videolan.org/x264.git x264<br />cd gpac<br />find . -name os_net.c | xargs perl -pi -e 's/u_long/unsigned long/g'<br />./configure<br />make lib<br />make install-lib<br /><br />cd ../x264<br />./configure --enable-mp4-output<br />make<br /></pre><br /><br />Then, to test that everything worked, run this:<br /><pre><br />wget notlime.com/2008/h264/foreman_part_qcif.yuv<br />./x264 -v -q 20 -o foreman.mp4 foreman_part_qcif.yuv 176x144<br />open foreman.mp4<br /></pre><br /><br />If you don't have <i>git</i> installed, you can find a nightly tarball of the x264 source code at <a href="ftp://ftp.videolan.org/pub/videolan/x264/snapshots/">ftp://ftp.videolan.org/pub/videolan/x264/snapshots/</a>. Hope this helps someone!Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com3tag:blogger.com,1999:blog-3246670076294002668.post-11082051185245701262008-09-02T21:38:00.002-04:002008-09-02T21:44:43.354-04:00Growing Triangle VinesWhen I was in school I was addicted to making <a href="http://www.processing.org">Processing</a> sketches. I haven't been as active recently, but made these in the past month and a half.<br /><br />The first is a visualization of a geometric computation that we used in the ICFP contest: <a href="http://notlime.com/2008/processing/arcsin_of_r_over_d/">Arcsin of R / D</a><br/><br />And the second comes from a pen-and-paper sketch made on a legal pad during my WTC tenure: <a href="http://notlime.com/2008/processing/iconic_growing_triangles/">Iconic Growing Triangles</a>Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com1tag:blogger.com,1999:blog-3246670076294002668.post-41218036405053450372008-08-26T22:52:00.004-04:002008-08-26T23:52:05.065-04:00Persistent RefactoringsRefactorings are usually <a href="http://www.science.uva.nl/~robbert/zappa/albums/Waka_Jawaka/03.html">one-shot deals</a>, triggered through an IDE, saved, committed, forgotten.<br /><br />Imagine for a moment though, that your revision control system was aware of refactorings, and recorded the refactoring command itself, not just the source text changes. You (or your IDE) might run this command:<br /><code><br />svn refactor pullup myFunction<br /></code><br /><br />Which would record the refactoring and which could <i>be used to inform merges</i> with other branches. Everyone loves easier merges of course, but if your automatic merge of two significantly-differently-structured-branches was nearly flawlessness, it would be possible to support two functionally equivalent, but architecturally different branches over a long timespan. In practice you could commit to either branch, and then pull from the other branch, relying on your version control system to refactor your changes so that the merge succeeded.<br /><br />Why do this?<br /><br />Perhaps you have a refactoring that reduces code-duplication but makes your codebase less readable, scannable, coherent. In this case you can branch and refactor, ending up with one easy-to-read branch, and one safe-to-modify-without-fear-of-missing-a-copy-pasted-version-of-the-same-function-in-another-module branch. Because the refactorings that we're considering here don't change the code functionally, these aren't really even branches, but simply two views on the same trunk.<br /><br />What other cases can you see this being handy for?Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com0tag:blogger.com,1999:blog-3246670076294002668.post-25843946895325310532008-07-30T14:00:00.002-04:002008-07-30T15:46:54.570-04:00Prolog Instantiation Modes (and Python exit contexts)I wrote <a href="http://code.google.com/p/python-macros/source/browse/trunk/return_context.py">a piece of Python code</a> that does a funny little transform on the syntax tree of a function, and creates a new function that returns all the local variables defined at the exit point of the original function. When I explain this to someone, they ask "Why?" and I don't have a good answer, but usually I say that it's related to predicates in Prolog that have multiple calling modes. Which I'm going to try explaining here:<br /><br />So, Prolog doesn't have functions, but it has something called "predicates" which are just as good. Predicates don't return a value, but any argument to a predicate can be an "output" variable, like a <a href="http://pages.cs.wisc.edu/~hasti/cs368/CppTutorial/NOTES/PARAMS.html#ref">C reference parameter</a>. Unlike C though, Prolog predicates often treat all of their parameters as outputs. For example, the function <tt>append</tt> can be used in (no less than) three different ways.<br /><pre><br />/* Appending, mode = input,input,output */<br />?- append([1,2,3],[4,5], X).<br />X = [1,2,3,4,5]<br /><br />/* Trimming off a shared starting sequence, mode = input,output,input */<br />?- append([1,2,3],X,[1,2,3,4,5]).<br />X = [4,5]<br /><br />/* Trimming off a shared ending sequence, mode = output,input,input */<br />?- append(X,[4,5],[1,2,3,4,5]).<br />X = [1,2,3]<br /></pre><br /><br />Through these three operations seem very different from the perspective of an imperative language, in Prolog <tt>append</tt> can be <a title="append([X|Y],Z,[X|W]) :- append(Y,Z,W). append([],X,X)." href="http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_7.html">defined in two simple lines</a>. The intuition about Prolog is that the runtime doesn't think of variables so much as inputs and outputs, but as "things I already know" and "thinks I don't know yet".<br /><br />We can translate Prolog's <a href="http://code.google.com/p/python-macros/source/browse/trunk/prology_append.py">append into Python</a> (at some loss of conciseness and functionality), and then use the Python macro mentioned above to check that the variable bindings at the end of the function maintain the invariant that we expect:<br /><pre><br />context = append_exit_context(None,[4,5],[1,2,3,4,5])<br />assert context['head'] + context['tail'] == context['result']<br /></pre><br /><br />So, this is pretty cool, we can pretend that we're writing a predicate instead of a function, assigning computed values to variables when we're able to discover them, and then examine those bindings after running the predicate.<br /><br />Of course, Prolog's <tt>append</tt> can also be called with the first two arguments uninstantiated, but that sort of magic is much harder to fit into Python.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com1tag:blogger.com,1999:blog-3246670076294002668.post-45764074119122224112008-07-19T22:29:00.001-04:002010-07-29T23:37:24.598-04:00Slow Sphinx IndexingTejus and I are building a Ruby on Rails site that needs both structured and unstructured search. Hamed suggested that we use <a href="http://blog.evanweaver.com/files/doc/fauna/ultrasphinx/files/README.html">Ultrasphinx</a>, a Rails plugin that provides an interface to the <a href="http://www.sphinxsearch.com/">Sphinx</a> search backend.<br /><br />I got everything downloaded and compiled, and had figured out how to debug the <tt>nil:NilClass</tt> errors that Ultrasphinx's configuration mini-language was generating, and then when I went to build the index for our database of seven documents... it seemed to hang. I was patient though, and let it run in the background for <b>10 minutes</b>. This might be acceptable on a huge database, but... it was clear that something was wrong.<br /><br />Several hours of debugging led me to the root cause: sphinx was assuming that the primary keys of the indexed table were sequential, and was creating a query for every 5000 rows between the min and max id of that table. With an auto_increment primary key, this is a valid assumption, but our data was being loaded by an <a href="http://wiki.rubyonrails.org/rails/pages/ActiveRecordYamlFixtures">ActiveRecord fixture</a> which was generating random primary keys, so the range between min and max was nearly a billion, thus the number of queries was in the hundreds of thousands, all but seven of them returning nothing.<br /><br />The solution of course, is to put explicit id's on your fixtures.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com2tag:blogger.com,1999:blog-3246670076294002668.post-49801615035805931722008-07-17T18:37:00.000-04:002008-07-17T19:05:17.662-04:00ICFP 2008Last weekend, I went over to the Monroe Drive House and wrote code for the <a href="http://www.icfpcontest.org/">International Conference on Functional Programming Contest</a>. Thankfully, the ICFP Contest doesn't require that your implementation language be purely functional (or even mostly functional), so we (Mark, Martin, and <a href="http://www.subwindow.com">Erik</a>) wrote our entry in python, using <a href="http://twistedmatrix.com/trac/">twisted</a> to handle network events. As we hacked on procedural code downstairs, <a href="http://oniugnip.livejournal.com/">Alex</a> and <a href="http://lindseykuper.livejournal.com/">Lindsey</a> wrote very pure Scheme code upstairs.<br /><br />We didn't do anything particularly fancy, just used a <a href="http://en.wikipedia.org/wiki/PID_controller">PID controller</a> to adjust the driver's angle towards the goal, and wrote some geometry routines to detect when we were on a collision course with an obstacle, and then plotted a course in whichever direction around the obstacle <i>looked</i> shorter. We also moved away from Martians if they were too close to us (and facing us). We talked about several more complex tactics, but didn't wind up with the extra time (or brainpower) to implement them.<br /><br />We had an awful version control experience with <a href="http://www.selenic.com/mercurial/wiki/">mercurial</a>: constant permissions errors in the remote repository, the need to manually "hg up" on the remote server, and flukey merges. I've had good luck in the past with mercurial on (a PyWeek entry) <a href="http://www.pyweek.org/e/etf/">stochasm</a>, and some of the trouble this time was because we were using an SSH repository, rather than the svnserve style that Drew setup on stochasm.<br /><br />Finally, <a href="http://notlime.com/2008/icfp2008.tgz">our entry, the code</a>.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com0tag:blogger.com,1999:blog-3246670076294002668.post-7677616863583617432008-05-23T18:03:00.001-04:002008-05-23T18:36:18.801-04:00Kitten NamingGabi and I have acquired a set of four kittens and a momma-cat. They're a bit wild, and prone to hissing, but we feed them, and they rumpus in our backyard.<br /><br />We named momma-cat "Olestra" because it has a classical ring to it, and gave the four kittens the names: Sprint, Cingular, (T-) Mobile, and Verizon. We dropped the "T dash" from Mobile's name because it was confusing - what does the "T" mean anyways? Both Sprint and Mobile are grey-tan tabbies, we're not sure which is which yet. Cingular is the fuzzy brown-black one, and Verizon is skinny and all-black.<br /><br />Naming critter-litters is a bit like <a href="http://blog.gtuhl.com/2007/05/25/server-naming-conventions/">naming servers</a>: you want to pick your names from a category that is roughly the same size as your things-to-be-named.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com2tag:blogger.com,1999:blog-3246670076294002668.post-45539720011358177502008-03-11T19:08:00.000-04:002008-03-11T19:27:07.090-04:00Avoiding ThreadDeath with env.js<p>At <a href="http://www.appcelerator.org">Appcelerator</a> we use <a href="http://ejohn.org/">John Resig</a>'s "<a href="http://ejohn.org/blog/bringing-the-browser-to-the-server/">simulated browser environment for Rhino</a>" as part of our IDE. I'd had intermittent problems with a <a href="http://java.sun.com/j2se/1.4.2/docs/api/java/lang/ThreadDeath.html">ThreadDeath</a> error being thrown, which would then cause any other thread running Rhino to hang.</p><br /><br /><p>I wasn't sure if the problem was in my Java code, my JavaScript, Rhino's Java code, or Aptana's Java code (we built our IDE atop their HTML/CSS/JS editor). Turns out it wasn't any of those! It was in that <a href="http://jqueryjs.googlecode.com/svn/trunk/jquery/build/runtest/env.js">"simulated browser environment" code</a>, in <tt>window.clearInterval</tt> where the thread spawned with <tt>setInterval</tt> is killed. I puzzled for a moment over why Mr.Resig was using multiple threads rather than a single one for setIntervals (expediency I assume), and then changed two lines so that it doesn't kill the thread, but allows it to die of natural causes.<br /><br /><pre><br /> window.setInterval = function(fn, time){<br /> var num = timers.length;<br /> <br /> timers[num] = new java.lang.Thread(new java.lang.Runnable({<br /> run: function(){<br /> <span style="background: #ffcccc">while (true) {</span><br /> <span style="background: #ccffcc">while (timers[num]) {</span><br /> java.lang.Thread.currentThread().sleep(time);<br /> fn();<br /> }<br /> }<br /> }));<br /> <br /> timers[num].start();<br /> <br /> return num;<br /> };<br /> <br /> window.clearInterval = function(num){<br /> if ( timers[num] ) {<br /> <span style="background: #ffcccc">timers[num].stop();</span><br /> delete timers[num];<br /> }<br /> };<br /></pre><br /><br />Another example of a day of debugging yielding a two line fix. Ugh.Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com2tag:blogger.com,1999:blog-3246670076294002668.post-76246579189679881512008-02-29T19:44:00.000-05:002008-03-06T17:56:18.812-05:00Dodging the DVCS Trainwreak<p>So what happens when the darcs or mercurial project goes <a href="http://www.redhat.com/magazine/010aug05/features/subversion/">the way of CVS</a> (that is: to bit-heaven)? How do you rescue your distributed repository from legacy-software-land?</p><br /><p>Well, the <a href="http://progetti.arstecnica.it/tailor">Tailor</a> project provides convertors between different repository formats, even some of the more obscure distributed VCSes. It seems to work in an all-at-once mode, rather than mirroring one live repository in other formats, but it does full history support, so...<br /><br />There's no harm in picking a bizarre distributed version control system today, if the project stalls, you can always upgrade your repository to whichever system becomes mainstream!Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com1tag:blogger.com,1999:blog-3246670076294002668.post-932561237819555492008-02-27T19:01:00.000-05:002008-03-13T19:30:33.712-04:00Atlhack distributed version control roundup<div><br />Alex writes <a href="http://penguinparens.blogspot.com/2008/02/todays-viewing-linus-on-git.html">about the advantages of git</a>, Erik shows us how to configure <a href="http://www.subwindow.com/articles/6">git to serve over http</a>, <a href="http://rockstarling.livejournal.com/">Lindsey</a> is using darcs, <a href="http://djfroofy.livejournal.com/">Drew</a> has been using mercurial for his personal projects (Miru, Yue), and I've been using darcs.<br /></div><br /><div><br />Are there any DVCSes we haven't tried? It seems that <a href="http://blog.ianbicking.org/dvcs-mini-roundup.html">Mr Bicking</a> has the full list.<br /></div>Markhttp://www.blogger.com/profile/00904617076470560132noreply@blogger.com0