Monday, July 22, 2019

Compiling Emacs on Mac OS against X11 libraries

Motivation

My place of work has been using Apple as the main, and now basically the only, supported platform for office use. As a long-time (GNU) Emacs user and occasional contributor, I usually compile GNU Emacs from the development (master) sources, which are now thankfully available over Git.
I already feel bad for using a proprietary OS rather than something based on GNU/Linux or another free or at least open source system. For this and other reasons, I try to at least use system libraries from the free/open source community rather than Apple's, for example for the GUI.  So rather than Apple's Carbon UI, I build Emacs against X11 libraries. Previously I could do this with the Gtk toolkit, but the maintainers of the Mac OS port of Gtk I was using stopped supporting its X11 drivers. So I reverted to the older "Lucid" toolkit with X11. (Yes, maybe I'm weird to cling to the X Window System in spite of the obstacles... that's probably because X was an important part of my socialization to Free Software and distributed systems.)

Howto

The prerequisites are
  • a bunch of packages from Homebrew (not all of which may be relevant):
    • autoconf autogen automake cairo d-bus dbus fontconfig freetype gcc gdk-pixbuf gettext git glib gmp gnutls gobject-introspection graphite2 harfbuzz imagemagick intltool ispell jansson jpeg json-glib libffi libpng librsvg libtasn1 libtiff libtool libunistring libxml2 little-cms2 netpbm nettle openjpeg openshift-cli osinfo-db osinfo-db-tools pcre pcre2 pkg-config readline shared-mime-info texinfo zlib
  • an X11 (XQuartz) installation with development headers
  • The Xcode development environment with its CLI tools installed.
I clone Emacs into /var/tmp/emacs/emacs according to the instructions on the Emacs from Git page of the Emacs Wiki. Then I mkdir /var/tmp/emacs/gbuild, cd there, and run
../emacs/configure --verbose \
  --with-x --with-x-toolkit=lucid --with-ns=no \
  --without-makeinfo \
  LIBXML2_CFLAGS=-I/usr/local/opt/libxml2/include/libxml2 \
  LIBXML2_LIBS='-L/usr/local/opt/libxml2/lib -lxml2' \
  --with-jpeg=no --with-gif=no --with-tiff=no \
  --x-libraries=/usr/local/opt/freetype/lib:/usr/X11/lib \
  --x-includes=/usr/local/opt/freetype/include:/usr/X11/include \
  --with-xpm=no \
  PKG_CONFIG_PATH=/usr/local/lib/pkgconfig:/usr/X11/lib/pkgconfig
This gives me the following configuration:
Configured for 'x86_64-apple-darwin18.6.0'.

  Where should the build process find the source code?    ../emacs
  What compiler should emacs be built with?               gcc -g3 -O2
  Should Emacs use the GNU version of malloc?             no
    (The GNU allocators don't work with this system configuration.)
  Should Emacs use a relocating allocator for buffers?    no
  Should Emacs use mmap(2) for buffer allocation?         no
  What window system should Emacs use?                    x11
  What toolkit should Emacs use?                          LUCID
  Where do we find X Windows header files?                /usr/local/opt/freetype/include:/usr/X11/include
  Where do we find X Windows libraries?                   /usr/local/opt/freetype/lib:/usr/X11/lib
  Does Emacs use -lXaw3d?                                 yes
  Does Emacs use -lXpm?                                   no
  Does Emacs use -ljpeg?                                  no
  Does Emacs use -ltiff?                                  no
  Does Emacs use a gif library?                           no
  Does Emacs use a png library?                           yes -L/usr/local/Cellar/libpng/1.6.37/lib -lpng16 -lz
  Does Emacs use -lrsvg-2?                                no
  Does Emacs use cairo?                                   no
  Does Emacs use -llcms2?                                 yes
  Does Emacs use imagemagick?                             no
  Does Emacs support sound?                               no
  Does Emacs use -lgpm?                                   no
  Does Emacs use -ldbus?                                  yes
  Does Emacs use -lgconf?                                 no
  Does Emacs use GSettings?                               no
  Does Emacs use a file notification library?             yes (kqueue)
  Does Emacs use access control lists?                    yes
  Does Emacs use -lselinux?                               no
  Does Emacs use -lgnutls?                                yes
  Does Emacs use -lxml2?                                  yes
  Does Emacs use -lfreetype?                              yes
  Does Emacs use HarfBuzz?                                yes
  Does Emacs use -lm17n-flt?                              no
  Does Emacs use -lotf?                                   no
  Does Emacs use -lxft?                                   yes
  Does Emacs use -lsystemd?                               no
  Does Emacs use -ljansson?                               yes
  Does Emacs use -lgmp?                                   yes
  Does Emacs directly use zlib?                           yes
  Does Emacs have dynamic modules support?                no
  Does Emacs use toolkit scroll bars?                     yes
  Does Emacs support Xwidgets (requires gtk3)?            no
  Does Emacs have threading support in lisp?              yes
  Does Emacs support the portable dumper?                 yes
  Does Emacs support legacy unexec dumping?               no
  Which dumping strategy does Emacs use?                  pdumper
Then I can build Emacs using
make bootstrap
This produces an intermediate "temacs" binary referencing many shared objects:
: 1leinen@macsl[leinen]; objdump -macho -dylibs-used /var/tmp/emacs/gbuild/src/temacs
/var/tmp/emacs/gbuild/src/temacs:
 /opt/X11/lib/libpng16.16.dylib (compatibility version 43.0.0, current version 43.0.0) /usr/lib/libz.1.dylib (compatibility version 1.0.0, current version 1.2.11) /opt/X11/lib/libXaw3d.8.dylib (compatibility version 9.0.0, current version 9.0.0) /opt/X11/lib/libXmu.6.dylib (compatibility version 9.0.0, current version 9.0.0) /opt/X11/lib/libXt.6.dylib (compatibility version 7.0.0, current version 7.0.0) /opt/X11/lib/libSM.6.dylib (compatibility version 7.0.0, current version 7.1.0) /opt/X11/lib/libICE.6.dylib (compatibility version 10.0.0, current version 10.0.0) /opt/X11/lib/libXext.6.dylib (compatibility version 11.0.0, current version 11.0.0) /opt/X11/lib/libX11.6.dylib (compatibility version 10.0.0, current version 10.0.0) /opt/X11/lib/libX11-xcb.1.dylib (compatibility version 2.0.0, current version 2.0.0) /opt/X11/lib/libxcb.1.dylib (compatibility version 3.0.0, current version 3.0.0) /opt/X11/lib/libXft.2.dylib (compatibility version 6.0.0, current version 6.2.0) /opt/X11/lib/libXrender.1.dylib (compatibility version 5.0.0, current version 5.0.0) /usr/local/opt/dbus/lib/libdbus-1.3.dylib (compatibility version 23.0.0, current version 23.11.0) /opt/X11/lib/libXrandr.2.dylib (compatibility version 5.0.0, current version 5.0.0) /opt/X11/lib/libXinerama.1.dylib (compatibility version 2.0.0, current version 2.0.0) /opt/X11/lib/libXfixes.3.dylib (compatibility version 5.0.0, current version 5.0.0) /usr/local/opt/libxml2/lib/libxml2.2.dylib (compatibility version 12.0.0, current version 12.9.0) /usr/lib/libncurses.5.4.dylib (compatibility version 5.4.0, current version 5.4.0) /usr/local/opt/freetype/lib/libfreetype.6.dylib (compatibility version 24.0.0, current version 24.1.0) /opt/X11/lib/libfontconfig.1.dylib (compatibility version 11.0.0, current version 11.2.0) /usr/local/opt/harfbuzz/lib/libharfbuzz.0.dylib (compatibility version 20504.0.0, current version 20504.0.0) /usr/local/opt/gnutls/lib/libgnutls.30.dylib (compatibility version 55.0.0, current version 55.0.0) /usr/local/opt/little-cms2/lib/liblcms2.2.dylib (compatibility version 3.0.0, current version 3.8.0) /usr/local/opt/jansson/lib/libjansson.4.dylib (compatibility version 16.0.0, current version 16.1.0) /usr/local/opt/gmp/lib/libgmp.10.dylib (compatibility version 14.0.0, current version 14.2.0) /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1252.250.1)
...and an src/emacs that hopefully doesn't crash. Oops... why am I saying that?
Well, yesterday I used a simpler method that didn't specify /usr/local/opt/freetype explicitly anywhere, but relied on autoconf/pkgconfig to find it. Unfortunately this created a "DLL hell" situation where an older version of the freetype dynamic library from /opt/X11/lib was used instead of the newer on in /usr/local/opt/freetype/lib, leading to crashes when Emacs tried to use certain fonts. Thanks to YAMAMOTO Mitsuharu for helping me find the error in my old build process!

Sunday, April 07, 2019

Google Code Jam 2019 in Lisp (again) - Qualification Round

Like most years, I registered for Google Code Jam again, because it's fun. The qualification round is usually easy for me to survive, but presents an opportunity to de-rust the brain, get used to coding and interacting with the competition platform.
Google introduced a new platform last year with a big change: Previously you got input and submitted output for checking, now you submit code, and Google runs it against input to check whether it generates the correct results. I suspect that a major driver for this change was the desire to curb cheating. The new platform also allows "interactive" problems, where your code interacts (via stdout/stdin) with a "judge" process, which is cool.
One sad effect of last year's move to the new platform was that I could no longer use Lisp—only a couple programming languages were supported. Thus I mostly used C last year.
This year I thought it was the same, and coded the first two problems, Foregone Solution and You Can Go Your Own Way, in C. As I started the third, I somehow noticed that more programming languages are supported this year, including Lisp (SBCL) and Clojure. So I changed to Common Lisp for problems three and four, Cryptopangrams and Dat Bae.
After fighting a little with the way the platform runs Lisp programs (I hadn't even known about SBCL's --script option), I managed to submit working versions for all problems.
When the ratings came out, it turned out that I had gotten the two difficult problems right including the (hidden) large datasets, but for the two easy problems, my results for the large inputs were bad: Wrong Answer for Foregone Solution and Runtime Error for You Can Go Your Own Way.
For the first, I had used strncpy() with a limit of MAXDIGITS, and forgot that if there are actually MAXDIGITS characters to copy, then strncpy() won't copy the terminating NUL, so I had to write that NUL byte to the end of the string, which I had failed to do.
For the second, I didn't read the problem description well, and thought that the problem size was limited to a 1000x1000 maze, where in fact it was 50000x50000 for the large set. Because I statically assigned vectors based on the maze edge length, this caused overruns. Easy to fix by changing a #define from 1000 to 50000.
Both bugs would have been unlikely in Lisp, where strings don't have to be NUL-terminated and dynamic allocation of data structures is more natural than fixed allocation.
Anyway, I lost 1+10 points to these stupid bugs, which gave me an overall score of 89. Of the more than 35500 participants, only one other person and I had this particular score. My rank was 1147, which is somewhat encouraging. But I was lucky to find good and easy-to-program approaches for each of the problems, and that will become (much) harder in the coming rounds.
For Foregone Solution, I noticed quickly that xx4x44x can be trivially split into xx3x33x and 0010110. For You Can Go Your Own Way, it took me a bit longer to come up with the "complement" solution, i.e. when Lydia has walked SSESEESE, then I can simply walk EESESSES and be sure that we both arrive at the same destination (because the maze is square) and never make the same move. With Cryptopangrams, I quickly had the correct intuition that I should compute the GCD of adjacent cryptosymbols to extract the common prime, and hacked together a version that would solve the two simple sample cases. But as I repeatedly failed the smaller input sets, I noticed that there are complications when symbols are repeated. This was when I resorted to pencil and paper—it would probably have been a good idea to start this earlier!—, and it took me a while to turn this into code. But when I thought I had it right, the system still wouldn't accept my solutions! That's when I found out that I have to actually call the (solve) function at the end of my program—doh!
For Dat Bae, I implemented the interaction with the Python-written sample judge using a subprocess, which allowed me to run local tests. The easier set (F=10 guesses for broken bits in up to 1024 total bits) was solved by numbering all 1024 bits. It took me a break to find that I could easily bring the number of guesses down to F=5 due to the constraint that not more than 15 bits are broken: This allowed me to use a smaller pattern (e.g. 0...31) and repeat it, without introducing any ambiguities.

Saturday, November 11, 2017

You say "the internet", I say "the Internet"...

My friend Nick Feamster recently twote something that resonated with me:
I still bristle whenever I read Internet with a lowercase "i".  The Internet is one specific instance of an "internetwork". People who write editorial style guides for tech should be required to take a networking class, or at least a history of networking class.
(The perspicacious reader will note that this happened after the 280calypse)
Having been involved for many years with the Internet, and the Internet Engineering Task Force, and the Internet Society, my first thought was "YES! Exactly this happens to me all the time."
But then I read the whole tweet, and much of the discussion, and found that I agree even more with Heather E. Merrick, who responded:
The AP Style Guide used to call for this but they grew up in 2016.
...especially after she countered Nick's remark that AP's editors "should clue up on history, and the use of proper nouns" with this explanation:
They used to, and then they wised up to the reality that language is not in the hands of any one person or industry but The People, who enjoy using a lowercase "i," hence the update to the Stylebook.
 Ratul Mahajan put it more succinctly (adding a friendly health tip):
inevitable success disaster
So you built the "Internet", and other people write about the "internet". My pro tip: Take it as a huge compliment: The thing you built has become an important part of their environment. Too vital to be considered some brand name anymore. But of course if you want to be sad about people "minimizing" your invention, that's your choice. Here's a kleenex for you!
Yes, I'll continue to write Internet with a capital I. Just like I write the name of my employer as "SWITCH" as we're told to, even though everybody always does it wrong and writes "Switch". But I stopped getting mad at those people, it's just not helpful. Instead I thank them for letting me continue to use the "correct" spelling.
When they tell me I have to stop, I'll just turn their internet off, that'll show them.

"...let's turn the turning off off", OK?

Sunday, April 30, 2017

Google Code Jam 2017 in Lisp: Round 1B/1C

Online round 1 was done on three dates again this year. The first (1A) fell in the middle of the night so I skipped it.

Round 1B Problem A: Steed 2: Cruise Control

I attempted the second, 1B, but I was distracted by important household chores. That's also why I didn't make any sketches. The first problem was easy enough, and I found a solution while fixing a meal for a kid who'd just returned from boy scout camp. The basic idea is that the horses all queue up behind the slowest one, so the arrival time is the latest arrival time at the destination point for all horses. The solution (A.lisp) worked fine on the first attempt of the small dataset, and also on the large one.

Round 1B Problem B: Stable Neigh-bors

The large dataset, where the unicorn's mane can have mixed colors, looked significantly more complex than the small one, where there are only three colors. I attempted a straightforward greedy algorithm, but somehow got it wrong. Because I didn't feel in a good state of mind, I decided to give up at that point. Otherwise I would have attempted the small dataset of Problem C: Pony Express. The "large dataset" cases of both problem B and problem C looked just too difficult to me.

Round 1C Problem A: Ample Syrup

A quick analysis suggested to me that the radius of the pancakes isn't relevant, because only the bottom (largest) one "counts", so I need to pick the pancakes with the largest lateral surface. Of course that reasoning was wrong, because we also need to pick which will be the bottom pancake. This error cost me two bad attempts, but I managed to reuse most of the initial code by adding a loop around it that tries various base pancakes. The code is in A.lisp and, again, worked fine for both the small and the large dataset.

Round 1C Problem B: Parenting Partnering

The optimization problem looked a bit tricky (but doable) in the general case, but the "small dataset" case was very specialized and easy enough to attack. There are only 1 or 2 activities in total. Either each partner has one, or one partner has all 1 or 2. If each partner has one, then the optimal solution always involves two exchanges. If one partner has the only one activity, the solution is even more trivially two exchanges. If one partner has (all) two activities, then the optimal solution is two if those activities can be arranged on the same "half-circle" (12 hours or 720 minutes) of the day, otherwise four. I coded these cases in B.lisp and was successful on the small dataset. In hindsight I'm surprised that it took me so long, more than 45 minutes between my submissions for A and for B-small.

Round 1C Problem C: Core Training

Next, I decided to try the small dataset of problem C. While I thought B-large might be in reach for me, I was sure that C-small was easy and could be coded quickly. (I had and still have no idea how I could successfully approach C-large.)
In particular, I thought that the training budget should always be spent on the worst (lowest-p) cores first. So I wrote this trivial loop, ahem, recursion, that spends as much as possible on those worst cores until either the budget is used up, or the worst cores become improved enough to be as good as the next-better core, or the cores reach p=1. But all my attempts were rejected,  and embarrassingly I still don't know why. Probably my reasoning was again oversimplified. Or it was something about the Lisp representation of floating point numbers. Anyway, the non-functioning code is in C.lisp.

Conclusion

This was the end of my participation in Google Code Jam 2017, because with rank #1850 I didn't make the cut—only the top 1000 in each of the round 1 sub-rounds make it to round 2. Even if I had been successful with the small dataset of C, I wouldn't have made the top 1000. Had I successfully solved the large dataset of B with some time to spare, then it might have worked.
It was mostly fun to code these small problems in Lisp. My Lisp skills are getting a bit rusty though. And I'm still not as comfortable with the SBCL/SLIME combination as I am with Allegro Common Lisp and its Emacs interface, but as I had mentioned in previous posts, I wanted to use completely free/open source software. And the awesome Allegro debugger wouldn't have been of much help here anyway.
And I love the problems! Kudos to the Googlers who come up with them.
How did the other Lispers fare? Badly as far as I can see. There haven't been many Lisp submissions in 2017 anyway, compared with 2016.

Friday, April 28, 2017

Enabling BBR on Ubuntu Xenial


BBR (Bottleneck Bandwidth and RTT) is a novel congestion control scheme for TCP. It was developed by several Google engineers and has been in use on Google.com and Youtube. See the PERT KB for more background.
Here's how you can enable it on a machine running Ubuntu 16.04 LTS "Xenial Xerus".
Note: This is mostly useful for systems that send fairly large TCP flows. And the configuration is incompatible with other packet schedulers such as fq_codel, so consider the tradeoff.

Upgrade Linux Kernel to ≥4.9

The BBR implementation was merged into the master branch of the Linux kernel before the 4.9 release. Xenial uses the 4.4 kernel by default, but you can install a newer one (4.10 as of this writing) from a preview repository of the "hardware enablement" kernel provided by Canonical:
sudo apt install -y --install-recommends \
  linux-generic-hwe-16.04-edge

Enable fq Packet Scheduler

BBR fundamentally requires a packet scheduler that can "pace" outgoing packets per flow.  Enable this by adding an "up" clause (shown in boldface below) to each interface in its corresponding configuration file, e.g. /etc/network/interfaces.d/eth0.cfg:

auto eth0
iface eth0 inet dhcp
  up tc qdisc replace dev $IFACE root fq pacing
iface eth0 inet6 auto

Make BBR the Default Congestion Control Algorithm for TCP

echo net.ipv4.tcp_congestion_control=bbr | \
  sudo tee /etc/sysctl.d/90-bbr

Activate by Rebooting

A reboot should now enable all necessary components: the recent kernel, a pacing-capable packet scheduler, and BBR as the default.
You can check whether BBR is actually in effect by using the ss -i command while having at least one TCP connection open—which is already guaranteed to be the case if you are logged in over SSH.
$ ss --tcp -i
State       Recv-Q Send-Q                                               Local Address:Port                                                                Peer Address:Port
ESTAB       0      1848                         2001:620:5ca1:2f0:f816:3eff:fe9c:71af:ssh                                                           2001:620:0:69::107:57795
  bbr wscale:5,7 rto:208 rtt:6.078/0.237 ato:48 mss:1182 cwnd:12 bytes_acked:156685 bytes_received:10033 segs_out:851 segs_in:977 send 18.7Mbps lastrcv:4 lastack:4 pacing_rate 87.2Mbps unacked:4 retrans:0/13 rcv_rtt:12 rcv_space:28560
ESTAB       0      0                            2001:620:5ca1:2f0:f816:3eff:fe9c:71af:ssh                                                           2001:620:0:69::107:61315
  bbr wscale:5,7 rto:220 rtt:18.674/25.752 ato:40 mss:1182 cwnd:11 bytes_acked:8025 bytes_received:5125 segs_out:86 segs_in:122 send 5.6Mbps lastsnd:470176 lastrcv:480332 lastack:470068 pacing_rate 60.5Mbps rcv_rtt:12 rcv_space:28560
The "-i" part of the output mentions "bbr" and includes some BBR-specific metrics as well as the pacing rate applied to each outbound TCP flow.