https://pinboard.in/u:jm/public/ recent bookmarks from jm 2017-05-15T10:23:27+00:00 https://shipilev.net/jvm-anatomy-park/10-string-intern/ jmString.intern is the gateway to native JVM String table, and it comes with caveats: throughput, memory footprint, pause time problems will await the users. Hand-rolled deduplicators/interners to reduce memory footprint are working much more reliably, because they are working on Java side, and also can be thrown away when done. GC-assisted String deduplication does alleviate things even more. In almost every project we were taking care of, removing String.intern from the hotpaths was the very profitable performance optimization. Do not use it without thinking, okay? ]]> strings interning java performance tips https://pinboard.in/ https://pinboard.in/u:jm/b:936351988ed0/ 2016-04-21T13:03:58+00:00 https://news.ycombinator.com/item?id=11535701 jm grep regular-expressions hacker-news strings dna genomics search elasticsearch https://pinboard.in/ https://pinboard.in/u:jm/b:c1dfd325084f/ 2016-03-24T12:07:15+00:00 http://left-pad.io/ jmA microservice saviour appears! In order to prevent such a terrible tragedy from occurring ever again during our lifetimes, `left-pad.io` has been created to provide all the functionality of `left-pad` AND the overhead of a TLS handshake and an HTTP request. Less code is better code, leave the heavy lifting to `left-pad.io`, The String Experts™. ]]> humor javascript jokes npm packages left-pad strings microservices http https://pinboard.in/ https://pinboard.in/u:jm/b:63260b4afafc/ 2015-10-21T14:33:51+00:00 https://github.com/01org/hyperscan jma high-performance multiple regex matching library. Hyperscan uses hybrid automata techniques to allow simultaneous matching of large numbers (up to tens of thousands) of regular expressions and for the matching of regular expressions across streams of data. Via Tony Finch]]> via:fanf regexps regex dpi hyperscan dfa nfa hybrid-automata text-matching matching text strings streams https://pinboard.in/ https://pinboard.in/u:jm/b:f41962a90f1b/ 2015-08-16T21:23:59+00:00 https://github.com/minimaxir/big-list-of-naughty-strings jm testing strings text data unicode utf-8 tests input corrupt https://pinboard.in/ https://pinboard.in/u:jm/b:c50633506c43/ 2014-10-27T22:15:46+00:00 http://lcamtuf.blogspot.ie/2014/10/psa-dont-run-strings-on-untrusted-files.html jmPerhaps simply by the virtue of being a part of that bundle, the strings utility tries to leverage the common libbfd infrastructure to detect supported executable formats and "optimize" the process by extracting text only from specific sections of the file. Unfortunately, the underlying library can be hardly described as safe: a quick pass with afl (and probably with any other competent fuzzer) quickly reveals a range of troubling and likely exploitable out-of-bounds crashes due to very limited range checking ]]> strings libbfd gnu security fuzzing buffer-overflows https://pinboard.in/ https://pinboard.in/u:jm/b:f30d5b5352c5/ 2014-08-29T21:55:32+00:00 https://github.com/cloudflare/lua-aho-corasick jm optimization speed performance aho-corasick tries string-matching strings algorithms lua c++ via:jgc https://pinboard.in/ https://pinboard.in/u:jm/b:35ea65a2e9a1/ 2014-06-18T09:22:13+00:00 https://blog.jcoglan.com/2014/06/17/utf-8-its-what-strings-are-made-of/ jmOnce again, I find myself checking over the UTF-8 validation code in websocket-driver, and once again I find I cannot ever remember how to make sense of this regex that performs the validation. I just copied it off a webpage once and it took a while (and reimplementing UTF-8 myself) to fully understand what it does. If you write software that processes text, you’ll probably need to understand this too. ]]> utf-8 unicode utf8 javascript node encoding text strings validation websockets regular-expressions regexps https://pinboard.in/ https://pinboard.in/u:jm/b:a7465566d88d/ 2014-03-31T13:44:45+00:00 http://blog.phusion.nl/2010/12/06/efficient-substring-searching/ jmTurbo Boyer-Moore is disappointing, its name doesn’t do it justice. In academia constant overhead doesn’t matter, but here we see that it matters a lot in practice. Turbo Boyer-Moore’s inner loop is so complex that we think we’re better off using the original Boyer-Moore. A good demo of how large values of O(n) can be slower than small values of O(mn).]]> algorithms search strings coding big-o string-search searching https://pinboard.in/ https://pinboard.in/u:jm/b:cad2a9fdecec/ 2014-01-20T15:43:05+00:00 http://www.mlsec.org/harry/ jma small tool for comparing strings and measuring their similarity. The tool supports several common distance and kernel functions for strings as well as some exotic similarity measures. The focus of Harry lies on implicit similarity measures, that is, comparison functions that do not give rise to an explicit vector space. Examples of such similarity measures are the Levenshtein distance and the Jaro-Winkler distance. For comparison Harry loads a set of strings from input, computes the specified similarity measure and writes a matrix of similarity values to output. The similarity measure can be computed based on the granularity of characters as well as words contained in the strings. The configuration of this process, such as the input format, the similarity measure and the output format, are specified in a configuration file and can be additionally refined using command-line options. Harry is implemented using OpenMP, such that the computation time for a set of strings scales linear with the number of available CPU cores. Moreover, efficient implementations of several similarity measures, effective caching of similarity values and low-overhead locking further speedup the computation. via kragen.]]> via:kragen strings similarity levenshtein-distance algorithms openmp jaro-winkler edit-distance cli commandline hamming-distance compression https://pinboard.in/ https://pinboard.in/u:jm/b:7f75587e4bd7/ 2013-04-29T10:32:24+00:00 http://courses.csail.mit.edu/6.851/spring12/lectures/ jmData structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms. This course covers major results and current directions of research in data structures: TIME TRAVEL We can remember the past efficiently (a technique called persistence), but in general it's difficult to change the past and see the outcomes on the present (retroactivity). So alas, Back To The Future isn't really possible. GEOMETRY When data has more than one dimension (e.g. maps, database tables). DYNAMIC OPTIMALITY Is there one binary search tree that's as good as all others? We still don't know, but we're close. MEMORY HIERARCHY Real computers have multiple levels of caches. We can optimize the number of cache misses, often without even knowing the size of the cache. HASHING Hashing is the most used data structure in computer science. And it's still an active area of research. INTEGERS Logarithmic time is too easy. By careful analysis of the information you're dealing with, you can often reduce the operation times substantially, sometimes even to constant. We will also cover lower bounds that illustrate when this is not possible. DYNAMIC GRAPHS A network link went down, or you just added or deleted a friend in a social network. We can still maintain essential information about the connectivity as it changes. STRINGS Searching for phrases in giant text (think Google or DNA). SUCCINCT Most “linear size” data structures you know are much larger than they need to be, often by an order of magnitude. Some data structures require almost no space beyond the raw data but are still fast (think heaps, but much cooler). (via Tim Freeman)]]> data-structures lectures mit video data algorithms coding csail strings integers hashing sorting bst memory https://pinboard.in/ https://pinboard.in/u:jm/b:5c72d87f4ea4/ 2013-04-23T20:33:04+00:00 http://isabel-drost.de/hadoop/slides/simon_lucene_2011.pdf jm benchmarks slides lucene search fuzzy-matching text-matching strings algorithms coding fsm tries https://pinboard.in/ https://pinboard.in/u:jm/b:90ddcc0d1fee/ 2013-01-27T22:46:47+00:00 http://www.strchr.com/strcmp_and_strlen_using_sse_4.2 jm sse optimization simd assembly intel i7 intel-core strstr strings string-matching strchr strlen coding https://pinboard.in/ https://pinboard.in/u:jm/b:dc8ab7793636/ 2013-01-18T11:21:08+00:00 http://arxiv.org/pdf/1209.6449.pdf jm rabin-karp algorithms strings string-matching papers via:fanf https://pinboard.in/ https://pinboard.in/u:jm/b:1a932a1f5d7e/ 2011-02-13T23:50:12+00:00 http://news.ycombinator.com/item?id=2208760 jm strings search algorithms burrows-wheeler-transform sequencing genome compression dna string-matching https://pinboard.in/u:jm/b:26291a82aeb8/