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 which has a name. Each leaf object refers to its successor forming a circular linked list. (The last leaf refers to the first.) Multiple interior nodes refer to each leaf object. A hash map containing every (strict) prefix of every name in the trie. Each prefix maps to a unique interior node. Names are treated as bit strings split into chunks of (say) 6 bits, and prefixes are whole numbers of chunks. An interior node contains a (1<<6) == 64 wide bitmap with a bit set for each chunk where prefix+chunk matches a key. Following the bitmap is a popcount-compressed array of references to the leaf objects that are the closest predecessor of the corresponding prefix+chunk key. Prefixes are strictly shorter than names so that we can avoid having to represent non-values after the end of a name, and so that it’s OK if one name is a prefix of another. The size of chunks and bitmaps might change; 6 is a guess that I expect will work OK. For restricted alphabets you can use something like my DNS trie name preparation trick to squash 8-bit chunks into sub-64-wide bitmaps. In Rust where cross-references are problematic, there might have to be a hash map that owns the leaf objects, so that the p-fast trie can refer to them by name. Or use a pool allocator and refer to leaf objects by numerical index. search To search, start by splitting the query string at its end into prefix + final chunk of bits. Look up the prefix in the hash map and check the chunk’s bit in the bitmap. If it’s set, you can return the corresponding leaf object because it’s either an exact match or the nearest predecessor. If it isn’t found, and you want the predecessor or successor, continue with a binary chop on the length of the query string. Look up the chopped prefix in the hash map. The next chunk is the chunk of bits in the query string immediately after the prefix. If the prefix is present and the next chunk’s bit is set, remember the chunk’s leaf pointer, make the prefix longer, and try again. If the prefix is present and the next chunk’s bit is not set and there’s a lesser bit that is set, return the leaf pointer for the lesser bit. Otherwise make the prefix shorter and try again. If the prefix isn’t present, make the prefix shorter and try again. When the binary chop bottoms out, return the longest-matching leaf you remembered. The leaf’s key and successor bracket the query string. modify When inserting a name, all its prefixes must be added to the hash map from longest to shortest. At the point where it finds that the prefix already exists, the insertion routine needs to walk down the (implicit) tree of successor keys, updating pointers that refer to the new leaf’s predecessor so they refer to the new leaf instead. Similarly, when deleting a name, remove every prefix from longest to shortest from the hash map where they only refer to this leaf. At the point where the prefix has sibling nodes, walk down the (implicit) tree of successor keys, updating pointers that refer to the deleted leaf so they refer to its predecessor instead. I can’t “just” use a concurrent hash map and expect these algorithms to be thread-safe, because they require multiple changes to the hashmaps. I wonder if the search routine can detect when the hash map is modified underneath it and retry. thoughts It isn’t obvious how a p-fast trie might compare to a qp-trie in practice. A p-fast trie will use a lot more memory than a qp-trie because it requires far more interior nodes. They need to exist so that the random-access binary chop knows whether to shorten or lengthen the prefix. To avoid wasting space the hash map keys should refer to names in leaf objects, instead of making lots of copies. This is probably tricky to get right. In a qp-trie the costly part of the lookup is less than O(k) because non-branching interior nodes are omitted. How does that compare to a p-fast trie’s O(log k)? Exact matches in a p-fast trie are just a hash map lookup. If they are worth optimizing then a qp-trie could also be augmented with a hash map. Many steps of a qp-trie search are checking short prefixes of the key near the root of the tree, which should be well cached. By contrast, a p-fast trie search will typically skip short prefixes and instead bounce around longer prefixes, which suggests its cache behaviour won’t be so friendly. A qp-trie predecessor/successor search requires two traversals, one to find the common prefix of the key and another to find the prefix’s predecessor/successor. A p-fast trie requires only one.

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.

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.

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

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