8 ms·
Adventures in Advent of Code
- stareatgoats 4y agoWhen your code fails it's never the fault of the language. It's always ones own fault, a typo, some error in the logic, or something. Debugging always reveals that with a stone face. Always. Except > "It turns out, there was a bug in Set.intersection(_:), but it had only been discovered this past June, and the fix hasn’t made it into a public version of Swift yet. "
- Avshalom 4y agoDon't know what to search for to bring it up but there's a story HN used to post occasionally about finding a CPU bug... talk about Always. Except.
- davedelong 4y ago(Hi, I'm the author of the post) It turns out the bug fix has been released publicly, but only on newer OS versions.
- mayoff 4y agoOr if you compile in release mode, in which case the fixed version is (maybe only sometimes?) inlined into your executable. I ran into the same bug, but since I'd included a `precondition` to verify that each elf-group had only one common item type, I discovered the bug immediately. I then needed about 5-10 minutes to convince myself that it really was a Swift bug and not a mayoff bug.
- frollo 4y agoYeah, luckily, those exceptions are really rare. Last time one happened to me I wasted three days before finding the culprit.
- smcl 4y agoAs someone who worked on C compilers for DSPs for a few years, I was conditioned for a while to think "compilers are broken, libraries are broken - you have no hope" for a while, when all I dealt with was our software. Obviously that's heavily influenced by what I was actually dealing with day to day and not by normal software development, but still :) One of the guys in my team handled a frantic support request from a Formula 1 team because they required reproducible builds or else they got some fine from the FIA, and they somehow hit a situation where our compiler was outputting different code depending on time of day. Wild.
- nappy-doo 4y agoFrom your description of the bug, I think even know which compiler you worked on. I worked on a competitors compiler. The state of embedded tools in the lates 90s and early 2000s was deplorable. I'm surprised we got anything working. (I went to work for the compiler team because I was so pissed off at how poorly they worked.)
- smcl 4y agoI should maybe have just said, it's not like it's sensitive information. It was @ Analog Devices, and given the engineer who was assigned to this bug I think it would have been for their TigerSHARC DSP. Trying to think who you might have worked for - Green Hills maybe? The compiler itself felt well-written and there were some very smart people involved in developing it. And now that I think about it the bug wasn't different code being output but some value elsewhere in the generated binary itself - maybe some ELF header? I wish I could remember
- nappy-doo 4y agoAh, I worked at ADI too. I rewrote the TigerSHARC register allocator (not adopted [complicated reasons, but Edinburgh wouldn't accept changes from the US]), and left the DSP group, and soon afterwards ADI. I thought you meant TI. Their compiler would compile in the date of compilation as a string by default (it wasn't deadcode eliminated in the linker because it was sucked in their panic libraries, if memory serves). In any case, yeah, ADI.
- hansvm 4y agoMiscompilations (interpretations) are fairly common in my experience; just most of them don't drastically affect the final result. I used to have a methodical way of investigating most bugs: (1) here's what I know, (2) here's what I don't, (3) here's the thing I would like to know to most restrict the remaining search space. It was fine enough for awhile, but when you don't know things like "I wrote a 0 here, therefore a 0 exists here", or "my code explicitly uses aligned 32-bit reads, so I issued an aligned 32-bit read here", the errors in your assumptions quickly get amplified into nonsense. Nowadays I explicitly includle miscompilation (interpretation), bit-flips, and other such garbage as I write down what I do or don't know about the system, and I throw in ballpark probabilities to figure out where to look next. Most debugging isn't noticably slower that way, but the hairy problems are easily 10x easier when you haven't conditioned yourself to ignore the real solution.
- benced 4y agoFor most engineers, you’ll have a handful of times in your career when the compiler or runtime really is the problem. The rest of the time it’s like 95% your fault and 5% the library’s fault.
- shaftoe444 4y agoI picked go for my language this year, which doesn't have good support for sets. May end up writing my own buggy implementation of this.
- angrais 4y agoWhat if you used a map and stored the value as a key? Then get all keys? Could work as a simple alternative and you could check if values are in it. Requires thinking if you want to implement set difference or intersection. I just figured depending on needs using existing built-in types may be fun.
- forrestthewoods 4y agoYou don't need a map for AoC 2022 day 3. There's only 52 elements. Which means a 64-bit bitmask is sufficient.
- shaftoe444 4y agoGreat idea!
- angrais 4y agoCould you expand on this, ideally with a python implementation?
- forrestthewoods 4y agoHere you go. https://pastebin.com/raw/BzEQ1bfe https://pastebin.com/raw/BzEQ1bfe For the problem we don't care how many instances of each letter occurs. We just need to know if there is 0 or 1 instance of a given letter. A set is a pretty good way to do this. Store a set of each "compartment", intersect the two sets, and you should have one value. We can do the same thing except instead of a set we use an integer and set bits. a-z are bits 0-26 and A_Z are bits 27-52. We can set a bit with bitwise-or. We can intersect two masks with bitwise-and. My code is probably a little too verbose. I'm not super familiar with python so I wasn't sure the best way to deal with characters and integers. But it's functional.
- forrestthewoods 4y agoHaving to update your entire OS to get bug fixes in a programming language is... not ideal.
- ninkendo 4y agoIt’s the way it works with libc too, right?
- 3836293648 4y agoThat depends on if you consider libc to be a part of the OS. Only the BSDs (including MacOS) do.
- mtlmtlmtlmtl 4y agoI'll be doing AoC in C this year. And I've decided to do that every year as I enjoy doing it in C and trying to get the entire calendar, all 50 parts to run in less than one second on a single core, which it turns out is quite doable, but only with a much deeper understanding of the problems. I end up learning a lot more computer science this way. I also like it since I don't do any work or even side projects in C these days, and so it's nice to keep my C chops up to scratch.
- disposedtrolley 4y agoNice! I’m writing in C this year too, although I’m very much a beginner in C. What kinds of optimisations have you had to do? Are you hosting your code anywhere?
- mtlmtlmtlmtl 4y agoFor doing it in C, by far the most useful thing you could do is implement your own generic hash table. Having a good hash table handy makes things a lot easier. Though since you're a beginner you might want to find a good library for it at first. Writing a hash table is great C exercise though, so I definitely recommend doing it at some point. I don't necessarily want to share my github as it contains my real name, but I'd be willing to send you a tarball of my 2020 code tomorrow if you send an email to mtlmtlmtlmtl at pm.me I've just now started on day 1 for this year, so no code there yet worth showing off.
- rashkov 4y agoI think I understand how to build a hash table except for one thing: which hash function should you use? Is there a simple one that’s good enough for most things? How do you pick one?
- tialaramex 4y agoif your hash table is a really good modern open addressed hash table, something like Google's Swiss Tables, you need a really good hash because you will be badly penalised otherwise, these modern structures demand a hash with proper behaviour for even halfway reasonable performance. If it's just a My First Hash table with closed addressing, buckets etc. you needn't care too much. If you're hashing integers, just use the integer itself, that's a terrible "hash" but with this like 1980s data structure it's good enough.
- satvikpendem 4y agoI'm doing AoC in ChatGPT this year: https://news.ycombinator.com/item?id=33821092 https://news.ycombinator.com/item?id=33821092
- jamamp 4y agoI'm confused. The post mentioned that this was fixed in Swift 5.7, but I have Swift 5.7.1 on my macOS Monterey and the bug is still present if I modify my AoC solution to exhibit the problem. Is Swift 5.7.1 on Monterey different from the 5.7.1 on Ventura? $ swift -v Apple Swift version 5.7.1 (swiftlang-5.7.1.135.3 clang-1400.0.29.51) Target: arm64-apple-macosx12.0 I love Swift as a language, but the lack of release notes for 5.7.1 (aside from a blog post for 5.7 as a whole), OS-specific releases (especially for SwiftUI), Xcode removing old toolchains when it upgrades (making me re-download tvOS 15.4 runtime for no reason), and all these other little things are starting to weigh on me.
- davedelong 4y agoTurns out the fix is only on Ventura. I was also on Monterey. I updated the blog post to include this.
- jamamp 4y agoBut that's my question. Similar to the other comment at https://news.ycombinator.com/item?id=33848354 https://news.ycombinator.com/item?id=33848354, I have 5.7.1 on Monterey. 5.7 isn't restricted to Ventura. Is the problem that the fix in 5.7/5.7.1 didn't actually fix it?
- Wevah 4y agoThe 5.7 compiler runs on Monterey, but the runtime is still 5.6, AIUI.
- js2 4y agoThe bug is apparently in the Swift runtime. You may be compiling with Swift 5.7.1, but you must be picking up the older runtime distributed with macOS 12.6. I think you can still run locally against a more recent Swift runtime though: https://news.ycombinator.com/item?id=33848354 https://news.ycombinator.com/item?id=33848354
- 4y ago
- js2 4y ago> The bug is fixed in Swift 5.7, but my computer is running macOS Monterey (12.6) and thus using an earlier version of Swift. I have since confirmed that the code works as expected on macOS Ventura. I guess the bug is apparently in the Swift runtime itself, and since Swift 5.0 and ABT stability, the runtime version is tied to the OS version. https://www.swift.org/blog/abi-stability-and-apple/ https://www.swift.org/blog/abi-stability-and-apple/ But I think that only applies to deployments via the App Store. I think for local development you can run against the current runtime by setting the TOOLCHAINS environment variable (you may also need to set SDKROOT). https://www.swift.org/getting-started/#on-macos https://www.swift.org/getting-started/#on-macos ETA. Apple does not make it easy to replace the runtime, but I got it to work like this: $ sw_vers ProductName: macOS ProductVersion: 12.6 BuildVersion: 21G115 $ cat foo.swift let a = "gnmCjzwnmCPTPhBwPjzBgqPjllJJSWlhfhQDSrpJRhDSlfJl" let b = "rLHNHrLHVNbVHMMctZFHsbcsDSDWpSDSGfSRsRWSRllfGSSG" let c = "NNtdMVrLNdZNvLvLZrzCndqBgwwPmwgjggBn" var s1 = Set(a) s1.formIntersection(b) s1.formIntersection(c) print(s1) var s2 = Set(a) s2.formIntersection(Set(b)) s2.formIntersection(Set(c)) print(s2) $ swiftc -version swift-driver version: 1.62.15 Apple Swift version 5.7.1 (swiftlang-5.7.1.135.3 clang-1400.0.29.51) Target: arm64-apple-macosx12.0 $ swiftc foo.swift $ ./foo ["P", "r", "C", "z", "w", "m", "B", "q", "j", "g", "n"] ["r"] $ otool -L foo foo: /usr/lib/libobjc.A.dylib (compatibility version 1.0.0, current version 228.0.0) /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1319.0.0) /usr/lib/swift/libswiftCore.dylib (compatibility version 1.0.0, current version $ DYLD_LIBRARY_PATH=/Library/Developer/Toolchains/swift-5.7.1-RELEASE.xctoolchain/usr/lib/swift/macosx ./foo ["r"] ["r"] Note that I had to download and install Swift 5.7.1 from swift.org. Trying to use libswiftCore.dylib from Xcode-14.1 is no bueno: $ /Applications/Xcode.app/Contents/Developer/usr/bin/xcodebuild -version Xcode 14.1 Build version 14B47b $ DYLD_LIBRARY_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/swift/macosx ./foo ["B", "P", "q", "C", "r", "n", "j", "w", "m", "z", "g"] ["r"] Oh, it's because /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/swift-5.0/macosx/libswiftCore.dylib is x86_64 only for some reason and I'm testing on an MBA M1. The dylibs under /Library/Developer/Toolchains/swift-5.7.1-RELEASE.xctoolchain/usr/lib/swift/macosx are arm64 and x86_64. WTF Apple?
- johnea 4y agoAdventures in Advent of Code <-- For people who really BELIEVE in the CODE! WTF HN?
- johnea 4y agoThe Truth Matters and Secular Humanists Should Defend It <-- The ADVENT of TRUTH! Wait, that would actually be a good thing...
- antirez 4y agoRelated: It's possible to simplify things using bitmaps: https://github.com/antirez/adventofcode2022/blob/main/day-3/2.c https://github.com/antirez/adventofcode2022/blob/main/day-3/...
- neonsunset 4y agoHey, just noticed our impls. for Day 2 look very similar. If you’re curious, Day 2 can be further improved by using modulo + 2 (or 1 if compiler is smart enough) branches instead of lookup table: https://github.com/neon-sunset/AOC2022/blob/main/Day2/Program.cs https://github.com/neon-sunset/AOC2022/blob/main/Day2/Progra...
- ZoomZoomZoom 4y agoIn which way do you reckon doing modular arithmetic is an improvement over two 3x3 look-up tables?
- neonsunset 4y agoThe rationale is as following - if the compiler cannot fold the lookup table, then math with 1-2 branches will be much cheaper because it involves no memory access and has constant (low) latency (keep in mind that when for example selecting a literal, a conditional select might be emitted which is usually cheaper than a regular branch e.g. Aarch64). In addition, unlike in C, in many other languages indexing into array will involve bounds check if the compiler cannot prove that the access is always in bounds. Obviously most branches will be predicted but branch retire throughput is always lower than math operations throughput.
- ZoomZoomZoom 4y agoThanks for the reply. The bounds checking is a valid reason I haven't thought of. In my case, using 3x3 array is roughly 3-4 times faster.
- rufus_foreman 4y agoNo I won't be participating in Advent of Code, and no, it is not one of the highlights of my holiday season. The highlights of my holiday season are stepping away from the keyboard and spending time with friends and family. The highlights of my holiday season do not include doing leetcode exercises, much as a I realize the need for leetcode exercises. So, no. I will not be participating in your Advent of Code.
- w-m 4y agoWow, Dave DeLong! A name that reminds me of learning Objective-C for an internship in 2010. As he was very active on Stackoverflow back then, and blogging too, maybe? I haven’t kept track much of Swift and the he Apple ecosystem since, but seeing this post brings back good memories.
- laacz 4y agoI'm doing AoC in Rust and Go. Go, because I got cozy with it during this year. With Rust, however, I never did. I tried, though. So let's try again.