Last post presented a narrowing division algorithm, but left some questions dangling around the interpretation of intermediate values. This post answers them. It presents an alternative derivation of the improved correction step, and shows how the true remainder may be computed from the estimated remainder. At the bottom are some benchmarks. Extending credit for the essential observation to Colin…
Announcing a port of Angband running entirely in-browser. Angband is a venerable roguelike dungeon-crawler set in the Tolkien universe. Click here to play it. There’s no sign-up or other nonsense. Some screenshots: Click on Unleash the Borg and watch it go. Click on Turbo and watch it go faster! This port compiles Angband to WASM using Emscripten. It uses a new front end not based on SDL or…
libdivide is fish ’s library for speeding up integer division by runtime constants. It works by replacing divide instructions with cheaper multiplications and shifts. libdivide supports SIMD, and recently gained support for AVX-512 and ARM NEON. Let’s benchmark on an Intel Xeon and Apple’s M1. Test Setup The microbenchmark is a sum-of-quotients function, like: uint32_t sumq ( const uint32_t * vals…
Last post explored Algorithm D, and some improvements for the 3 ÷ 2 = 1 digit case. This post presents a narrowing division algorithm, improving upon the widely used “divlu” function from Hacker’s Delight. I am optimistic that these ideas are original. divlu is a narrowing division: it divides a 4 digit number by a 2 digit number, producing a 2 digit quotient and remainder. This is achieved by…
Algorithm D is Knuth's celebrated multiword integer division algorithm. This post tries to make Algorithm D approachable, and also has an idea for an improvement, in the last section. A followup post provides code to take advantage of that improvement. To build intuition, we'll use concrete base-10 values, instead of a general base and digit count like Knuth does. It should be straightforward to…
My least favorite Rust type is std::ops::Range . Range is a foundational type, with magic syntax but a simple definition : struct Range < Idx > { /// The lower bound of the range (inclusive). pub start : Idx , /// The upper bound of the range (exclusive). pub end : Idx , } Idx is typically an integral type, but you can make a Range of anything, which will become important later. Here’s a range of…
JavaScript rounds in a tricky way. It tricked all the engines, and even itself. Math.round() behaves the same as C’s familiar round with one key difference: it rounds halfways (“is biased”) towards positive infinity. Here is its spec in ES 5.1 . It suggests an implementation too: The value of Math.round(x) is the same as the value of Math.floor(x+0.5)... And so every engine did that .…
At very small scales, particles are described by wavefunctions that obey the Schrödinger Equation. What do wavefunctions look like? The Wavefiz is a nifty visualizer that draws them! It's real physics: we're solving the Schrödinger Equation in real time with arbitrary potentials. But it's also just plain fun to play with! There's some non-mathy exercises to do too. Have you heard of the ground…
The Amazon Dash is a $5 WiFi button that summons a truck to deliver you water or other stuff. Want your Dash to do something else? The popular approach is to sniff its ARP requests. This requires that Dash connect to your network, putting you perilously close to having some DUDE delivered with your IoT mood lighting. A more immediate problem is immediacy, or lack thereof: the Dash button only…
fish 2.0 is now released! fish is a fully-equipped command line shell (like bash or zsh) that is smart and user-friendly. fish supports powerful features like syntax highlighting, autosuggestions, and tab completions that just work, with nothing to learn or configure. Go get it: http://fishshell.com This marks the first release of fish in over four years, and includes many new features, fixes, and…
"Asswipe," replied Yahoo's server. That's when I knew I had it. Yahoo's public chat rooms have passed away . It is for the best, for the spam had spread everywhere. But they had a good run, operating for a decade and a half, an Internet eternity. Here are three funny stories from the Yahoo chat protocol. Body and Zoul Yahoo chat rooms started life as a Java applet, chugging along in Netscape…
This post was written sixteen months ago, when fish briefly explored Go with the intention of writing a new command line shell. ( fish abandoned Go after discovering that terminal programming is what makes shells so horrible, and term programming is least horrible in C.) These are some notes fish took as he explored Go, and as a result they're mostly unstructured, unbalanced, and surface-level.…
No. But this is the closest yet! The new fish is a POSIX command line shell with delightful, intuitive features like autosuggestions , 256 color syntax highlighting , web based configuration , and lots more. Best of all, these features just work , out of the box. No arcane syntax, no twiddling obscure knobs. It runs inside your favorite terminal emulator, such as Terminal.app, xterm, or iTerm.…
Hex Fiend 2.1 is here. Hex Fiend is a fast and clever open source hex editor for Mac OS X. Notable new features include: A binary diff viewer Support for reading raw devices (after authentication, natch) Selectable string encoding for the text view Bookmarks Transient untitled documents (aka "reuse that empty Untitled window") Undo preserved across saves, if it can be done efficiently Fresh new…
This post is available in a less handy format . There's also a PDF . Comments and discussion are on reddit . This is a technique fish thought up for improving the performance of unsigned integer division by certain "uncooperative" constants. It does not seem to appear in the literature, nor is it implemented in gcc, llvm, or icc, so fish is optimistic that it is original. As is well known (and…
Angband 3.3. Best to read this one on the site.
I am at work, heading to a meeting, walking down an empty hallway. As I reach the end, the door opens from the other side, and Steve enters, looking down intently at his iPhone. I step aside so he can pass, but he stops right in the middle of the doorway. He doesn't see me. I wait. He pokes at his phone. I nervously shuffle my feet. He still is just standing there. Do I dare clear my throat? Five…
This is the true story of the app that was fixed by a crash. We travel back to join fish mid-debugging: I'm dumbfounded. The thread is just gone. And not just any thread: the main thread. I don't even know how you make the main thread go away. exit() gets rid of the whole app. Will pthread_exit() do it? Maybe it's some crazy exception thing? See, I've got a bug report. Surf's Up: Epic Waves…
Maybe you've got a list of things, like friends or appointments or map locations, and you want to give each one its own color so the user can distinguish them easily. The user can make new friends or appointments, so you don't know ahead of time how many colors you'll need. And when the user adds a new item, you want its color to be as different from all other colors as possible, to avoid…
ridiculous_fish now comes with 90% less scrolling and 100% less commenting. Comments can be posted on the relevant reddit or Hacker News threads, or tweet @ridiculous_fish to tell fish he’s full of carp.
Speaking of integer division, here's a nice library that performs the multiply-and-shift optimization at runtime. It does vectors too. Cool!
See how well you know (or can anticipate) gcc's optimizer. For each question, the left box contains some code, while the right box contains code that purports to do the same thing, but that illustrates a particular optimization. Will gcc apply that optimization? Put another way, will the code on the left be as fast as the code on the right, when compiled with an optimizing gcc? I used a pretty…
Here's how you divide an unsigned int by 13 in C: unsigned divide(unsigned x) { return x / 13; } It gets better, I promise. Here's the corresponding x64 assembly that gcc produces: _divide: movl $1321528399, %edx movl %edi, %eax mull %edx shrl $2, %edx movl %edx, %eax ret Instead of division, there's multiplication by a bizarre number: 1321528399. What wickedness is this? 1321528399 is an example…
Quick, what is " char (*(*(* const x[3])())[5])(int) ?" If you immediately blurted out " x­is­an­array­of­three­const­pointers­to­functions­returning­pointers­to­arrays­of­five­pointers­to­functions­taking­int­returning­char ", and your last name doesn't end with "itchie," then chances are you used my new…
This is the second episode of I Didn't Order That, So Why Is It On My Bill: C++ features you never use, but pay for anyways. See episode one here . For those who like their punchlines first: std::string is designed to allow copy-on-write. But once operator[] is called, that string is ruined for COW forevermore. The reason is that it has to guard against a future write at any time, because you may…
Hooray, it's Hex Fiend 2, a nearly complete rewrite of Hex Fiend that incorporates even better techniques for working with big files. Hex Fiend is my fast and clever hex editor for Mac OS X. Click On Me To Get Hex Fiend This app is about exploring the implementation of standard desktop UI features in the realm of files too large to fully read into main memory. Is it possible to do copy and paste,…
C++ was designed to ensure you "only pay for what you use," and at that it is mostly successful. But it's not entirely successful, and I thought it might be interesting to explore some counterexamples: C++ features you don't use but still negatively impact performance, and ways in which other languages avoid those issues. So here's the first episode of I Didn't Order That, So Why Is It On My Bill,…
This post is in homage to my old page, a triumph of curvaceousness . May it sleep roundly. As any usability expert will tell you, the foundation of sound web page design is rounded corners. Their smooth curves lend an organic, almost sensual feel to a site, while other pages are un-navigable morasses of right angles. Rounded corners are easy with tables and images! But tables make your page Web…
Buzz is leaving Apple, has already left. Buzz joined Apple two months after I joined, on the same team. He was the first candidate I ever interviewed, although I can't remember what I asked him. Without Buzz's encouragement and inspiration, I'd have never started this blog, and he was first to link to me. So thank you and farewell, Buzz. On another thread, I've fixed the Angband screensaver to…
Guest blogger: Gollum (Smeagol) Where isst it? So it iss back - so fissh , the fish, raw and wriggling, he hasst brought its back! Angband, the Hells of Iron, yest, the ancient ASCII roguelike, child spawn of Moria and VMS, it iss here once more. We wants it! You hasst not seen it, Angband? But perhapss you have seen one like it, the filthy, filthy NetHack , yess, full of such stupids and jokeses,…
" That's a lot of cores. And while 80-core floating point monsters like that aren't likely to show up in an iMac any time soon, multicore chips in multiprocessor computers are here today. Single chip machines are so 2004. Programmers better get crackin'. The megahertz free ride is over - and we have work to do." There, that's the noisome little pitch everyone's been spreading like so much thermal…
Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio! Hair care! Digital audio!
Hex Fiend 1.1.1 is now available open source under a BSD-style license. Hex Fiend is my fast and clever free open source hex editor for Mac OS X. I hope you find Hex Fiend useful for whatever purpose, but if you are interested in contributing changes on an ongoing basis, I'll be happy to grant Subversion commit privileges to some interested developers who submit quality patches. There is a wiki…
A Brief History Mac OS 9 and NEXTSTEP were like two icy comets wandering aimlessly in space. Neither was really going anywhere in particular. And then, BANG! They collide, stick wetly together, spinning wildly! Thus was born Mac OS X - or so the legend goes. How do you take these two comets, err, operating systems, and make a unified OS out of them? On the one hand, you have the procedural classic…
Spiffy! Hex Fiend version 1.1 is ready. Hex Fiend is my fast and clever free hex editor for Mac OS X. New stuff: Horizontal resizing Custom fonts Overwrite mode Hidden files Lots more goodies (see release notes) Hex Fiend 1.1 May you find it useful! Wake up. Ssnsnrk. Wake up, he's gone. Zzzz...wha? Oh, someone's here. Allow me to spin up. .... .... .... .... .... .... .... .... .... .... If it's…
Old age and treachery will beat youth and skill every time. "I'm going to beat grep by thirty percent!" I confidently crow to anyone who would listen, those foolish enough to enter my office. And my girlfriend too, who's contractually obligated to pay attention to everything I say. See, I was working on Hex Fiend , and searching was dog slow. But Hex Fiend is supposed to be fast , and I want…
The latest "OS X is slow" meme to impinge on the mass psyche of the Internet comes courtesy of one Jasjeet Sekhon, an associate professor of political science at UC Berkeley. The page has hit digg and reddit and been quoted on Slashdot. The article and benchmark is here . Is there any merit to this? Once again, this discussion is only my meager opinion. I do not speak for Apple, and none of what I…
One of my side projects has borne some fruit. Meet Hex Fiend, a new hex editor for Mac OS X. (Hex editors allow you to edit the binary data of a file in hexadecimal or ASCII formats.) Click here to read more, see screenshots, or download Hex Fiend Hex Fiend allows inserting and deleting as well as overwriting data. It supports 100+ GB files with ease. It provides a full undo stack, copy and paste,…
aaron: Howdy George. george: Hey Aaron! How's the C programming coming? aaron: Not so good. It doesn't support all the things I'm used to, from other programming languages. Where's the garbage collection? Where's the type safety? Where's the lexically scoped functions? george: Yeah, ISO standard C is pretty anemic. Wait, lexus-what? aaron: Lexically scoped functions. You know, nested functions -…
Our arrays, aren't . There, that's known as a teaser. You see it in television all the time. "Find out which common household plant devours pets at night... but first ." And then you have to sit through and watch the stuff about Brad and Angelina shacking up / Shaq driving his new Hummer / Hummer's new fragrance before they get to the good stuff, the petnivorous plants. I don't know what I'd do…
Why now? My friend over at SciFiHiFi suggests that Microsoft likes trees, but Apple likes hash tables . Well, I think that Microsoft prefers integer arithmetic, while Apple (or at least Cocoa) likes floating point. Here's a bunch of examples I found: Take color. Microsoft's API (you know, THAT one) makes colors from integer components , but Cocoa makes colors from floats . Microsoft does sliders…
Well, they found me. I knew it was only a matter of time. It happens to every blog. Comment spam, and a lot of it. But nobody told me it would be like this! I got about 200 messages an hour. I mean, the attention is flattering, but still, my goodness! Let's see what we can do about that. (If you hate math and all you care about is how to post a comment, go to The Punchline ) π This fish was a…
Sending messages can be fun! All you have to do is make a game of it. What kind of game, you ask? Well, for example, we could see how many we can send in four seconds, then try to beat that record. (Apologies to Bart and Principal Skinner.) Objective-C is a dynamic language. When you send a message to an object, gcc emits a call to objc_msgSend() or one of its specialized, similiar functions.…
Ancient programmers speak in hushed tones of the legend known as the "compiled bitmap." Ok, no they don't, but there is such a thing. It's a technique that was sometimes used in the DOS days for rapidly drawing an image to the screen. But how can you compile a bitmap? And is there any value remaining in this technique, or should it be left in the dustbin along side TSRs and DOSSHELL? Let's find…
I'm sure you've seen it too, 'cause it was on Slashdot and if you're fishing here, you're definitely an online junkie. I'm talking about that Anandtech article, of course. The one that tries to compare OS X to Linux and a PowerPC to an x86. Lemme see... this one . No more mysteries, they promise! None of it's pleasant, but what's the worst part? The mySQL results . I know it's painful - you don't…
What does sending a message to nil do in Objective-C? What value does it return? You probably know that if the method is declared to return an object, you get back nil, but what if the method is declared to return a char? An int? A long long? A float? A struct? And how does it all work? Let's find out! objc_msgSend Here's what I do know. When you send a message to an object, such as [someObject…
I'm a developer on Apple's AppKit team; I work to make Cocoa better. With a few exceptions, we are responsible for both AppKit and Foundation . This is my blog. You can contact me at corydoras@ridiculousfish.com Description forthcoming.