## GTA 的啟動讀取效能問題

```struct {
uint64_t *hash;
item_t   *item;
} entry;```

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

• hook strlen
• wait for a long string
• “cache” the start and length of it
• if it’s called again within the string’s range, return cached value

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

## JavaScript 的 sort 變成 stable

Firefox 則是很久前就決定使用 Merge sort 了 (看了一下，當時還在從 Firebird 轉換名稱到 Firefox 的時期)：「Array.sort isn't a stable sort (switch to MergeSort)」。

Timsort 是 1993 年發明出來的演算法，與 Merge sort 的情況類似，除了 stable 外，還可以保證最差的情境下的時間複雜度是 $O(n*log(n))$

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.

## 自動校正字幕時間的軟體 subsync

Language-agnostic automatic synchronization of subtitles to video, so that subtitles are aligned to the correct starting point within the video.

• Discretize video and subtitles by time into 10ms windows.
• For each 10ms window, determine whether that window contains speech. This is trivial to do for subtitles (we just determine whether any subtitle is "on" during each time window); for video, use an off-the-shelf voice activity detector (VAD) like the one built into webrtc.
• Now we have two binary strings: one for the subtitles, and one for the video. Try to align these strings by matching 0's with 0's and 1's with 1's. We score these alignments as (# matching digits) - (# mismatched digits).

## V8 version 6.5 (Chrome 65) 的改變

V8 version 6.5 將會有不少改變：「V8 release v6.5」。

In response to the latest speculative side-channel attack called Spectre, V8 introduced an untrusted code mode. If you embed V8, consider leveraging this mode in case your application processes user-generated, not-trustworthy code. Please note that the mode is enabled by default, including in Chrome.

For the graph below we measure the time it takes to download and compile a WebAssembly module with 67 MB and about 190,000 functions. We do the measurements with 25 Mbit/sec, 50 Mbit/sec, and 100 Mbit/sec download speed.

## PHP 提供的資料結構...

PHPDatastructures 說明目前 PHP SPL 所支援的 data structure，在記憶體用量以及效率上面都會比自己實作來的小且快。