Full Width [alt+shift+f] Shortcuts [alt+shift+k]
Sign Up [alt+shift+s] Log In [alt+shift+l]
4
Here’s a sketch of an idea that might or might not be a good idea. Dunno if it’s similar to something already described in the literature – if you know of something, please let me know via the links in the footer! The gist is to throw away the tree and interior pointers from a qp-trie. Instead, the p-fast trie is stored using a hash map organized into stratified levels, where each level corresponds to a prefix of the key. Exact-match lookups are normal O(1) hash map lookups. Predecessor / successor searches use binary chop on the length of the key. Where a qp-trie search is O(k), where k is the length of the key, a p-fast trie search is O(log k). This smaller O(log k) bound is why I call it a “p-fast trie” by analogy with the x-fast trie, which has O(log log N) query time. (The “p” is for popcount.) I’m not sure if this asymptotic improvement is likely to be effective in practice; see my thoughts towards the end of this note. layout A p-fast trie consists of: Leaf objects, each of...
17 hours ago

Improve your reading experience

Logged in users get linked directly to articles resulting in a better reading experience. Please login for free, it takes less than 1 minute.

More from Tony Finch's blog

clamp / median / range

Here are a few tangentially-related ideas vaguely near the theme of comparison operators. comparison style clamp style clamp is median clamp in range range style style clash? comparison style Some languages such as BCPL, Icon, Python have chained comparison operators, like if min <= x <= max: ... In languages without chained comparison, I like to write comparisons as if they were chained, like, if min <= x && x <= max { // ... } A rule of thumb is to prefer less than (or equal) operators and avoid greater than. In a sequence of comparisons, order values from (expected) least to greatest. clamp style The clamp() function ensures a value is between some min and max, def clamp(min, x, max): if x < min: return min if max < x: return max return x I like to order its arguments matching the expected order of the values, following my rule of thumb for comparisons. (I used that flavour of clamp() in my article about GCRA.) But I seem to be unusual in this preference, based on a few examples I have seen recently. clamp is median Last month, Fabian Giesen pointed out a way to resolve this difference of opinion: A function that returns the median of three values is equivalent to a clamp() function that doesn’t care about the order of its arguments. This version is written so that it returns NaN if any of its arguments is NaN. (When an argument is NaN, both of its comparisons will be false.) fn med3(a: f64, b: f64, c: f64) -> f64 { match (a <= b, b <= c, c <= a) { (false, false, false) => f64::NAN, (false, false, true) => b, // a > b > c (false, true, false) => a, // c > a > b (false, true, true) => c, // b <= c <= a (true, false, false) => c, // b > c > a (true, false, true) => a, // c <= a <= b (true, true, false) => b, // a <= b <= c (true, true, true) => b, // a == b == c } } When two of its arguments are constant, med3() should compile to the same code as a simple clamp(); but med3()’s misuse-resistance comes at a small cost when the arguments are not known at compile time. clamp in range If your language has proper range types, there is a nicer way to make clamp() resistant to misuse: fn clamp(x: f64, r: RangeInclusive<f64>) -> f64 { let (&min,&max) = (r.start(), r.end()); if x < min { return min } if max < x { return max } return x; } let x = clamp(x, MIN..=MAX); range style For a long time I have been fond of the idea of a simple counting for loop that matches the syntax of chained comparisons, like for min <= x <= max: ... By itself this is silly: too cute and too ad-hoc. I’m also dissatisfied with the range or slice syntax in basically every programming language I’ve seen. I thought it might be nice if the cute comparison and iteration syntaxes were aspects of a more generally useful range syntax, but I couldn’t make it work. Until recently when I realised I could make use of prefix or mixfix syntax, instead of confining myself to infix. So now my fantasy pet range syntax looks like >= min < max // half-open >= min <= max // inclusive And you might use it in a pattern match if x is >= min < max { // ... } Or as an iterator for x in >= min < max { // ... } Or to take a slice xs[>= min < max] style clash? It’s kind of ironic that these range examples don’t follow the left-to-right, lesser-to-greater rule of thumb that this post started off with. (x is not lexically between min and max!) But that rule of thumb is really intended for languages such as C that don’t have ranges. Careful stylistic conventions can help to avoid mistakes in nontrivial conditional expressions. It’s much better if language and library features reduce the need for nontrivial conditions and catch mistakes automatically.

a month ago 21 votes
Golang and Let's Encrypt: a free software story

Here’s a story from nearly 10 years ago. the bug I think it was my friend Richard Kettlewell who told me about a bug he encountered with Let’s Encrypt in its early days in autumn 2015: it was failing to validate mail domains correctly. the context At the time I had previously been responsible for Cambridge University’s email anti-spam system for about 10 years, and in 2014 I had been given responsibility for Cambridge University’s DNS. So I knew how Let’s Encrypt should validate mail domains. Let’s Encrypt was about one year old. Unusually, the code that runs their operations, Boulder, is free software and open to external contributors. Boulder is written in Golang, and I had not previously written any code in Golang. But its reputation is to be easy to get to grips with. So, in principle, the bug was straightforward for me to fix. How difficult would it be as a Golang newbie? And what would Let’s Encrypt’s contribution process be like? the hack I cloned the Boulder repository and had a look around the code. As is pretty typical, there are a couple of stages to fixing a bug in an unfamiliar codebase: work out where the problem is try to understand if the obvious fix could be better In this case, I remember discovering a relatively substantial TODO item that intersected with the bug. I can’t remember the details, but I think there were wider issues with DNS lookups in Boulder. I decided it made sense to fix the immediate problem without getting involved in things that would require discussion with Let’s Encrypt staff. I faffed around with the code and pushed something that looked like it might work. A fun thing about this hack is that I never got a working Boulder test setup on my workstation (or even Golang, I think!) – I just relied on the Let’s Encrypt cloud test setup. The feedback time was very slow, but it was tolerable for a simple one-off change. the fix My pull request was small, +48-14. After a couple of rounds of review and within a few days, it was merged and put into production! A pleasing result. the upshot I thought Golang (at least as it was used in the Boulder codebase) was as easy to get to grips with as promised. I did not touch it again until several years later, because there was no need to, but it seemed fine. I was very impressed by the Let’s Encrypt continuous integration and automated testing setup, and by their low-friction workflow for external contributors. One of my fastest drive-by patches to get into worldwide production. My fix was always going to be temporary, and all trace of it was overwritten years ago. It’s good when “temporary” turns out to be true! the point I was reminded of this story in the pub this evening, and I thought it was worth writing down. It demonstrated to me that Let’s Encrypt really were doing all the good stuff they said they were doing. So thank you to Let’s Encrypt for providing an exemplary service and for giving me a happy little anecdote.

a month ago 26 votes
performance of random floats

A couple of years ago I wrote about random floating point numbers. In that article I was mainly concerned about how neat the code is, and I didn’t pay attention to its performance. Recently, a comment from Oliver Hunt and a blog post from Alisa Sireneva prompted me to wonder if I made an unwarranted assumption. So I wrote a little benchmark, which you can find in pcg-dxsm.git. As a brief recap, there are two basic ways to convert a random integer to a floating point number between 0.0 and 1.0: Use bit fiddling to construct an integer whose format matches a float between 1.0 and 2.0; this is the same span as the result but with a simpler exponent. Bitcast the integer to a float and subtract 1.0 to get the result. Shift the integer down to the same range as the mantissa, convert to float, then multiply by a scaling factor that reduces it to the desired range. This produces one more bit of randomness than the bithacking conversion. (There are other less basic ways.) My benchmark has 2 x 2 x 2 tests: bithacking vs multiplying 32 bit vs 64 bit sequential integers vs random integers Each operation is isolated from the benchmark loop by putting it in a separate translation unit (to prevent the compiler from inlining) and there is a fence instruction (ISB SY on ARM, MFENCE on AMD) in the loop to stop the CPU from overlapping successive iterations. I ran the benchmark on my Apple M1 Pro and my AMD Ryzen 7950X. In the table below, the leftmost column is the number of random bits. The top half measures sequential numbers, the bottom half is random numbers. The times are nanoseconds per operation, which includes the overheads of the benchmark loop and function call. arm amd 23 12.15 11.22 24 13.37 11.21 52 12.11 11.02 53 13.38 11.20 23 14.75 12.62 24 15.85 12.81 52 16.78 14.23 53 18.02 14.41 The times vary a little from run to run but the difference in speed of the various loops is reasonably consistent. I think my conclusion is that the bithacking conversion is about 1ns faster than the multiply conversion on my ARM box. There’s a subnanosecond difference on my AMD box which might indicate that the conversion takes different amounts of time depending on the value? Dunno.

a month ago 27 votes
moka pot notes

In hot weather I like to drink my coffee in an iced latte. To make it, I have a very large Bialetti Moka Express. Recently when I got it going again after a winter of disuse, it took me a couple of attempts to get the technique right, so here are some notes as a reminder to my future self next year. It’s worth noting that I’m not fussy about my coffee: I usually drink pre-ground beans from the supermarket, with cream (in winter hot coffee) or milk and ice. basic principle When I was getting the hang of my moka pot, I learned from YouTube coffee geeks such as James Hoffmann that the main aim is for the water to be pushed through the coffee smoothly and gently. Better to err on the side of too little flow than too much. I have not had much success trying to make fine temperature adjustments while the coffee is brewing, because the big moka pot has a lot of thermal inertia: it takes a long time for any change in gas level to have any effect on on the coffee flow. routine fill the kettle and turn it on put the moka pot’s basket in a mug to keep it stable fill it with coffee (mine needs about 4 Aeropress scoops) tamp it down firmly [1] when the kettle has boiled, fill the base of the pot to just below the pressure valve (which is also just below the filter screen in the basket) insert the coffee basket, making sure there are no stray grounds around the edge where the seal will mate screw on the upper chamber firmly put it on a small gas ring turned up to the max [2] leave the lid open and wait for the coffee to emerge immediately turn the gas down to the minimum [3] the coffee should now come out in a steady thin stream without spluttering or stalling when the upper chamber is filled near the mouths of the central spout, it’ll start fizzing or spluttering [4] turn off the gas and pour the coffee into a carafe notes If I don’t tamp the grounds, the pot tends to splutter. I guess tamping gives the puck better integrity to resist channelling, and to keep the water under even pressure. Might be an effect of the relatively coarse supermarket grind? It takes a long time to get the pot back up to boiling point and I’m not sure that heating it up slower helps. The main risk, I think, is overshooting the ideal steady brewing state too much, but: With my moka pot on my hob the lowest gas flow on the smallest rings is just enough to keep the coffee flowing without stalling. The flow when the coffee first emerges is relatively fast, and it slows to the steady state several seconds after I turn the heat down, so I think the overshoot isn’t too bad. This routine turns almost all of the water into coffee, which Hoffmann suggests is a good result, and a sign that the pressure and temperature aren’t getting too high.

2 months ago 21 votes

More in programming

Extending My Japanese Visa as a Freelancer

With TokyoDev as my sponsor, I extended my Engineer/Specialist in Humanities/International Services visa for another three years. I’m thrilled by this result, because my family and I recently moved to a small town in Kansai and have been enjoying our lives in Japan more than ever. Since I have some experience with bureaucracy in Japan, I was prepared for things to get . . . complicated. Instead, I was pleasantly surprised. Despite the fact that I’d changed jobs and had three dependents, the process was much simpler than I expected. Below I’ll share my particular experience, which should be especially helpful to those in the Kansai area, and cover the following: What a visa extension is What happens when you change jobs mid-visa The documents your new sponsoring company needs to provide The documents you need to assemble yourself Some paperwork issues you might encounter What you can expect when visiting an immigration office (particularly in Osaka) Follow-up actions you’ll be required to take Information I wish I’d had What do I mean by “visa extension”? In 2022, I was a permanent employee at a company in Tokyo, which agreed to sponsor my Engineer/Specialist in Humanities/International Services visa and bring me to Japan. Initially I received a three-year work visa, and at the same time my husband and two children each received a three-year Dependent visa. Our original visas were set to expire in August 2025, but we’ve decided to remain in Japan long-term, so we wanted to prolong our stay. Since Japan’s immigration offices accept visa extension applications beginning three months before the visa end date, I began preparing my application in May 2025 and submitted it in June. It’s a good idea to begin the visa extension process as soon as possible. There are no downsides to doing so, and beginning early can help prevent serious complications. If you have a bank account in Japan, it can be frozen when your original visa expires; you will either need to show the bank your new residence card before that date, or demonstrate that you are currently in the process of extending your visa. Your My Number Card also expires on the original visa expiration date. This process is also often called a “visa renewal,” but it’s the same procedure. There is no difference between an extension and a renewal. New employment status and employer In the three years since my visa was originally issued, I became a freelancer, or sole proprietor (個人事業主, kojin jigyou nushi), and left my original sponsoring company. Paul McMahon was not only one of my first clients in Japan, but also the first to offer me an ongoing contract, which was enormously helpful. When I made my formal exit from my initial company, I was able to list TokyoDev as my new employer when notifying Immigration. The documents required TokyoDev also agreed to sponsor my visa, which meant Paul would provide documentation about the company to Immigration. I’d assumed this paperwork might be difficult or time-intensive, but Paul reassured me that the entire process was quite simple and only took a few hours. This work does not increase linearly per international employee; once a company knows which documents are required, it is relatively simple to repeat the process for each employee. I’m not the first worker TokyoDev has sponsored. In fact, TokyoDev successfully sponsored a contractor within a month of incorporation, with the only fees being those required for gathering the paperwork. Company documents Exactly what documents are required varies according to the status of the company. In this specific case, the documents Paul provided for TokyoDev, a category 4 company, were: The company portion of my visa extension application TokyoDev’s legal report summary (法定調書合計表, hotei chosho goukei-hyou) for the previous fiscal year TokyoDev’s Certificate of Registration (登記事項証明書, touki jikou shoumei-sho) A copy of TokyoDev’s financial statements (決算書, kessan-sho) for the latest fiscal year A business description of TokyoDev, which in this case was a sales presentation in Japanese that explained the premise of the company Personal documents The documents I supplied myself were: My passport and residence card My portions of my visa extension application A visa-sized photo (taken at a photo booth) The signed contract between myself and TokyoDev A contract with a secondary client My tax payment certificate for the previous year (納税証明書, nouzei shoumei-sho), which I got from our town hall My resident tax certificate (住民税の課税, juuminzei no kazei), which I got from our town hall I had to prepare some additional documents for my dependents. These were: The residence cards and passports of my children Copies of my own residence card and passport, for my husband’s application Visa extension applications for my dependent children and husband A visa-sized photo of my husband (children under 16 don’t need photos) Copies and Japanese translations of the children’s birth certificates A copy and Japanese translation of our American wedding certificate Paperwork tips A few questions and complications did arise while I was assembling the paperwork. Japanese translations I had Japanese translations of my children’s birth certificates and my marriage certificate already, left over from registering my initial address with City Hall. These translations were done by a coworker, and weren’t certified. I’ve used them repeatedly for procedures in Japan and never had them rejected. Dependent applications First, I had a hard time locating the correct application for my dependents. I could only find the one I’ve linked above, which initially didn’t seem to apply, since it’s for dependents of those who have a Designated Activities visa (such as researchers). I ended up filling out another, totally erroneous version of the application and had to re-do it all at the immigration office. To my chagrin, I found the paper version they had on hand was identical to this linked form! Resident tax certificate in a new town Next, my resident tax certificate was complicated by the fact that I’d lived in my new town in Nara for about seven months, and hadn’t yet paid any resident tax locally. Fortunately my first resident tax installment came due about that time, so I paid it promptly, then got the form from City Hall demonstrating that it had indeed been paid. I wasn’t sure a single payment would be enough to satisfy immigration, but it seemed to work. If I’d needed to prove payment for previous years, I would have had to request that certificate from the previous town I’d lived in, Hachoiji. Since this would have been a tedious process involving mailing things back and forth and a money order, I was glad to avoid it. Giving a “reason for extension” When filling out my application, Paul advised that I ask for a five-year extension: he said Immigration might not grant it, but it probably wouldn’t hurt my chances. I did that, and in the brief space where you write “Reason for extension,” I crammed in several sentences about how my career is based in Japan, my husband is studying shakuhachi, and my children attend public Japanese school and speak Japanese. All our applications included at least some of these details. This probably wasn’t necessary, and it’s hard to say if it influenced the final result or not, but that was how I approached it. That pesky middle name I worried that since I’d signed my TokyoDev contract without my middle name, which is present on my passport and residence card, that the application would be rejected. This sort of name-based nitpicking is common enough at Japanese banks—would Immigration react in the same way? Paul assured me that other employees had submitted their contracts without middle names and had no trouble. He was right and it wasn’t an issue, but I’ve decided in future to sign everything with all three of my names, just to be sure. Never make this mistake Finally, my husband wrote his own application, then had to rewrite it at the immigration office because they realized he’d used a Frixion (erasable) pen. This is strictly not allowed, so save yourself some trouble and use a regular ballpoint with blue or black ink! The application process Before making the trip to an immigration office, I polled my friends and checked Google Maps reviews. The nearest office to me had some one-star reviews, and a friend of mine described a negative experience there, so I was leery of simply going with the closest option. Instead, I decided to apply at an office farther from home, the Osaka Regional Immigration Bureau by Cosmosquare Station, which my friend had used for years. I wasn’t entirely sure that this was permitted, but nobody at the Osaka office raised an eyebrow at my Nara address. Getting there I took the train to Cosmosquare Station and arrived around lunchtime on Friday, June 20th. The station itself has an odd quirk: every time I try to use Google Maps inside or near it, I receive bizarrely inaccurate directions. Whatever the building is made of, it really messes with Maps! Luckily the signage around Cosmosquare is quite clear, and I had no difficulty locating the immigration office once I stopped trying to use my phone. Unfortunately I must have picked one of the worst times to visit. The office is on the second floor, but the line extended out the door and down the staircase. At least it was moving quickly, and I soon discovered that there is a convenience store on the second floor, which proved important later on. Asking for information The line I was standing in led to two counters, Application and Information. Since I wasn’t sure I had filled out the correct forms for my dependents, I stopped by the Information desk first. The man there spoke English well, and informed me that I had, in fact, filled out the wrong paperwork. This mistake was easily fixed because there were printed copies of the correct form—and of every other form used by Immigration—right by the doorway. The clerk also confirmed what I’d already suspected, that I couldn’t submit an application on behalf of my husband. Since I’d come alone while he watched the kids, he’d have to come by himself later. I took fresh copies of the applications for my children. Since the office itself was quite full, I went to the convenience store and enjoyed a soda while filling out the paperwork again. That convenience store also has an ID photo booth, a copier, and revenue stamps, so it’s well-equipped to assist applicants. Submitting the application Armed with the correct paperwork, I got back into line and waited around 10 minutes for my turn to submit. The woman behind the desk glanced quickly through my documents. Mostly she wanted to know if I needed to make any copies, because I wouldn’t be receiving these documents back. Once I’d confirmed I didn’t need any papers returned, she gave me a number and asked me to wait to be called. In addition to my number, she handed me a postcard on which to write my own address. This would be sent to me if and when Immigration approved the visa extension, to indicate by what date I needed to pick up my new residence card. Based on the messages I periodically sent my husband, my number wasn’t called for three and a half hours. The office was crowded and hot, but there were also screens showing the numbers called in the hallway and downstairs in the lobby, so it’s possible to visit the convenience store or stretch your legs without missing your appointment. Being able to purchase snacks and drinks at will certainly helped. Mostly, I wished I had brought a good book with me. When my number was finally called, I was surprised they had no questions for me. The clerks had spotted one place in the documents where I’d forgotten to sign; once that minor error was corrected, I was free to go. A paper was stapled into my passport, and my residence card was stamped on the back to show that I was going through the visa extension process. My husband’s experience My husband visited the Osaka Regional Immigration Bureau at 9:30 a.m. on Monday, June 26th. Although he described it as “quite busy” already, there was no line down the staircase, and he was finished by noon. If you want to avoid long wait times, arriving early in the morning might help. Approval and picking up Given the crowd that had packed the Osaka immigration office, and also knowing how backed up the immigration offices in Tokyo can be, I fully expected not to see our postcards for several months. Immigration regularly publishes statistics on the various visas and related processing times based on national averages. In fact, my husband and I received our postcards the same day, July 11th, just three weeks after I’d submitted my and my children’s applications. As usual, there was no indication on the postcard as to how long our visa extension would be: we would only find out if we’d qualified for a one-, three-, or five-year extension once we picked up our new residence cards. I had until July 18th to collect the cards for myself and the kids, and my husband had until the 25th to get his. We opted to go together on the same day, July 14th. The postcards also indicated that we’d need four 6,000 yen revenue stamps, one for each applicant. Revenue stamps (収入印紙, shuunyuu inshi) are a cash replacement, like a money order, to affix to specific documents. Though we knew that the convenience store at the Osaka Regional Immigration Bureau sold revenue stamps, we decided to secure them in advance, just in case. The morning we left, we stopped by our local post office and showed the staff our postcards. They had no trouble identifying and providing the stamps we needed. We arrived at the immigration office around 10:45 a.m. Foolishly, we’d assumed that picking up the cards would be a faster process. Instead, we waited for nearly four hours. Fortunately we’d discussed this possibility with several family friends, who were prepared to help pick up our children from school when we were running late. We finally got our cards and the news was good: we’d all received three-year extensions! Aftermath Extending our visa, and receiving new residence cards, entails some further paperwork. Specifically: My husband will need to reapply for permission to work. We’ll need new My Number cards for all family members, as those expire with the original visa expiration date. Our Japanese bank account will also be frozen upon the original visa expiration date, so it’s important that we inform our bank of the visa extension and provide copies of our new cards as soon as possible. If you are still going through the extension process when your original visa expires, you can show the bank your residence card, which should be stamped to indicate you are currently extending your visa, to prevent them from freezing your account in the interim. Top Takeaways Here’s a brief list of the most important questions I had during the process, and the answers I found. Can I apply for a visa extension on behalf of my spouse and children? Yes to underage children, no to the spouse, unless there are serious extenuating circumstances (such as the spouse being hospitalized). If you and your spouse don’t apply at the same time, make sure your dependent spouse has a copy of your passport and residence card to take with them. Can you only apply at the nearest immigration office? Not necessarily. I applied to one slightly further from my house, and actually in another prefecture, for personal reasons. However, this only worked because the Osaka office was a regional branch, with broader jurisdiction that included Nara. It probably wouldn’t have worked in reverse—for example, if I lived in Osaka and applied to the satellite office in Nara, which only has jurisdiction over Nara and Wakayama. Be sure to check the jurisdiction of the immigration office you choose. Is there any downside to applying early? There is no downside to getting your application in as soon as possible. Immigration will begin accepting applications within three months of the visa expiration date. I originally questioned whether an early extension would mean you “lost” a few months of your visa. For example, if I received my new card in June, but my visa was originally due to expire in August, would the new expiration date be in June? This isn’t the case: the new expiration date is based on the previous expiration date, not on when you submit your application. My visa’s prior expiration date was August 2025, and it’s now August 2028. If you’re extending a visa that was for longer than one year, how many years of tax certificates and records do you need to provide? A: I only provided my previous fiscal year’s tax certificate and proof of one resident tax payment in my local area, and that seemed to be enough. I wasn’t asked for documentation of previous years or paperwork from my prior town hall. Conclusion I’ve lived in several countries over the last fifteen years, so I’m experienced in general at acquiring and retaining visas. Japan’s visa system is paperwork-intensive, but it’s also fair, stable, and reasonably transparent. The fact that my Japanese visa isn’t attached to a singular company, but rather to the type of work I wish to perform, gives me peace of mind as I continue to establish our lives here. I also feel more comfortable as a freelancer in Japan, now that I know how easy it is for a company to sponsor my visa. Paul was able to assemble the documents needed in a single afternoon, and it didn’t cost TokyoDev anything beyond the price of the papers and postage. As freelancing and gig work are on the rise, I’d encourage more Japanese companies to consider sponsoring visas for their international contractors. Likewise, I hope that the experience I’ve shared here will help other immigrants to explore their freelancing options in Japan, and approach their visa extension process with both good information and a solid plan. If you’d like to continue the conversation on visa extensions and company sponsorship, you can join the TokyoDev Discord. Or see more articles on visas for developers, starting your own business in Japan, and remaining here long-term.

15 hours ago 4 votes
We Are Still the Web

Twenty years ago, Kevin Kelly wrote an absolutely seminal piece for Wired. This week is a great opportunity to look back at it. The post We Are Still the Web appeared first on The History of the Web.

2 hours ago 2 votes
A Few Things About the Anchor Element’s href You Might Not Have Known

I’ve written previously about reloading a document using only HTML but that got me thinking: What are all the values you can put in an anchor tag’s href attribute? Well, I looked around. I found some things I already knew about, e.g. Link protocols like mailto:, tel:, sms: and javascript: which deal with specific ways of handling links. Protocol-relative links, e.g. href="//" Text fragments for linking to specific pieces of text on a page, e.g. href="#:~:text=foo" But I also found some things I didn’t know about (or only vaguely knew about) so I wrote them down in an attempt to remember them. href="#" Scrolls to the top of a document. I knew that. But I’m writing because #top will also scroll to the top if there isn’t another element with id="top" in the document. I didn’t know that. (Spec: “If decodedFragment is an ASCII case-insensitive match for the string top, then return the top of the document.”) href="" Reloads the current page, preserving the search string but removing the hash string (if present). URL href="" resolves to /path/ /path/ /path/#foo /path/ /path/?id=foo /path/?id=foo /path/?id=foo#bar /path/?id=foo href="." Reloads the current page, removing both the search and hash strings (if present). Note: If you’re using href="." as a link to the current page, ensure your URLs have a trailing slash or you may get surprising navigation behavior. The path is interpreted as a file, so "." resolves to the parent directory of the current location. URL href="." resolves to /path / /path#foo / /path?id=foo / /path/ /path/ /path/#foo /path/ /path/?id=foo /path/ /path/index.html /path/ href="?" Reloads the current page, removing both the search and hash strings (if present). However, it preserves the ? character. Note: Unlike href=".", trailing slashes don’t matter. The search parameters will be removed but the path will be preserved as-is. URL href="?" resolves to /path /path? /path#foo /path? /path?id=foo /path? /path?id=foo#bar /path? /index.html /index.html? href="data:" You can make links that navigate to data URLs. The super-readable version of this would be: <a href="data:text/plain,hello world"> View plain text data URL </a> But you probably want data: URLs to be encoded so you don’t get unexpected behavior, e.g. <a href="data:text/plain,hello%20world"> View plain text data URL </a> Go ahead and try it (FYI: may not work in your user agent). Here’s a plain-text file and an HTML file. href="video.mp4#t=10,20" Media fragments allow linking to specific parts of a media file, like audio or video. For example, video.mp4#t=10,20 links to a video. It starts play at 10 seconds, and stops it at 20 seconds. (Support is limited at the time of this writing.) See For Yourself I tested a lot of this stuff in the browser and via JS. I think I got all these right. Thanks to JavaScript’s URL constructor (and the ability to pass a base URL), I could programmatically explore how a lot of these href’s would resolve. Here’s a snippet of the test code I wrote. You can copy/paste this in your console and they should all pass 🤞 const assertions = [ // Preserves search string but strips hash // x -> { search: '?...', hash: '' } { href: '', location: '/path', resolves_to: '/path' }, { href: '', location: '/path/', resolves_to: '/path/' }, { href: '', location: '/path/#foo', resolves_to: '/path/' }, { href: '', location: '/path/?id=foo', resolves_to: '/path/?id=foo' }, { href: '', location: '/path/?id=foo#bar', resolves_to: '/path/?id=foo' }, // Strips search and hash strings // x -> { search: '', hash: '' } { href: '.', location: '/path', resolves_to: '/' }, { href: '.', location: `/path#foo`, resolves_to: `/` }, { href: '.', location: `/path?id=foo`, resolves_to: `/` }, { href: '.', location: `/path/`, resolves_to: `/path/` }, { href: '.', location: `/path/#foo`, resolves_to: `/path/` }, { href: '.', location: `/path/?id=foo`, resolves_to: `/path/` }, { href: '.', location: `/path/index.html`, resolves_to: `/path/` }, // Strips search parameters and hash string, // but preserves search delimeter (`?`) // x -> { search: '?', hash: '' } { href: '?', location: '/path', resolves_to: '/path?' }, { href: '?', location: '/path#foo', resolves_to: '/path?' }, { href: '?', location: '/path?id=foo', resolves_to: '/path?' }, { href: '?', location: '/path/', resolves_to: '/path/?' }, { href: '?', location: '/path/?id=foo#bar', resolves_to: '/path/?' }, { href: '?', location: '/index.html#foo', resolves_to: '/index.html?'} ]; const assertions_evaluated = assertions.map(({ href, location, resolves_to }) => { const domain = 'https://example.com'; const expected = new URL(href, domain + location).toString(); const received = new URL(domain + resolves_to).toString(); return { href, location, expected: expected.replace(domain, ''), received: received.replace(domain, ''), passed: expected === received }; }); console.table(assertions_evaluated); Email · Mastodon · Bluesky

2 days ago 5 votes
Big O vs Hardware: Better Complexity ≠ Better Performance

Why Your O(log n) Algorithm Might Lose to O(n)

2 days ago 7 votes