Manifest (performance improvement) #182

notcancername · 2023-01-31T17:53:32Z

WIP

This will probably be replaced by a hash-based manifest given the official site has 530K files.....

This PR will add support for the manifest.txt proposed in #85. It's expected to bring performance improvements. Closes #85.

Description

The manifest is optional. It must located at the root of the base URL, with the name manifest.txt. It must contain a list of LF, CRLF, LFCR, or CR-terminated paths, relative to the base URL. A path is made up of components, separated by either / or \. Each path component must not include any of the bytes /, \, LF, or CR. If the manifest is present, it must contain paths of all files and directories accessible to the client. A manifest may include a leading empty path component or a leading . path component. However, this is discouraged. The manifest should be sorted in ascending order.

Design issues

LF and CR are used as separators. Thus, paths may not contain LF or CR. This is done for ease of generation with find . >manifest.txt or whatever the Windows equivalent is. To fix this, escaping and/or zero-termination may be used instead.
\ is a valid path separator. Thus, /-separated path components may not contain \. This is done for compatibility with Windows.
Mixing \ and / path component separators is allowed. This is inelegant, but easy to process.

Implementation issues

Currently, we use binary search to determine whether an element exists. Thus, we will have to make log2(n)+1 comparisons in the worst case. This is not an issue for vanilla, a vanilla manifest is about 3000 paths and the worst case number of comparisons is 13. Also, storing all the flle paths wastes space and causes a bunch of cache misses. Consider using a hash set.
I kept the old fileExists to not break the API. Look into removing it.

Practical issues

In my testing, the fact that all the URLs are specified in lower case but the actual paths are sentence case caused issues. Not sure how to address that other than to specify it correctly.
I am a complete beginner at both JS and TS and have never done webdev. Please, PLEASE check all the code very thoroughly. While I have tested everything both with and without a manifest, I might still have fucked something up unknowingly.

Salanto · 2023-01-31T19:08:08Z

In my testing, the fact that all the URLs are specified in lower case but the actual paths are sentence case caused issues. Not sure how to address that other than to specify it correctly.

Convert to lowercase, lol. AO should've adopted a standard for content spelling years ago.

notcancername · 2023-01-31T19:21:55Z

@Salanto That's what I ended up doing.

stonedDiscord

holy shit it actually became real

stonedDiscord · 2023-01-31T23:06:39Z

the windows command is
dir /S /B /A:-D > manifest.txt
and then you have to remove the absolute paths

testing booboo

notcancername · 2023-01-31T23:36:02Z

@stonedDiscord You said manfred's sprites don't load anymore after you add the manifest?

notcancername · 2023-01-31T23:43:20Z

confirmed, I guess?
That didn't happen on my test server 🤔
The fact that it's 24(!!!) MB is concerning. We probably need a new approach.

notcancername · 2023-02-01T00:21:05Z

I'm closing this. 24 Megs per WebAO session is not tolerable.

caleb-mabry · 2023-02-01T00:13:52Z

webAO/utils/getAnimLength.js

@@ -11,7 +13,7 @@ const getAnimLength = async (url) => {
  const extensions = ['.gif', '.webp', '.apng'];
  for (const extension of extensions) {
    const urlWithExtension = url + extension;
-    const exists = await fileExists(urlWithExtension);
+      const exists = await fileExistsManifest(urlWithExtension);


I think there's some extra spacing here

caleb-mabry · 2023-02-01T00:21:36Z

webAO/utils/fileExists.js

+ * Otherwise, look it up in the manifest */
+const fileExistsManifest = async (url) =>
+      new Promise((resolve, reject) => {
+          if(client.manifest.length == 0) {


=== here please

caleb-mabry · 2023-02-01T00:22:34Z

webAO/utils/fileExists.js

+              resolve(fileExists(url));
+              return;
+          }
+          const c_url = encodeURI(canonicalizePath(decodeURI(url.slice(AO_HOST.length))));


In general, JS uses camel case, so it may be a good idea to stick with that schema. Also calling it the full canonical.
Kinda nitpicking that since c has to be slightly interpreted

caleb-mabry · 2023-02-01T00:24:15Z

webAO/client/setEmote.ts

    } else {
      url = `${characterFolder}${encodeURI(charactername)}/${encodeURI(
        prefix
      )}${encodeURI(emotename)}${extension}`;
    }
-    const exists = await fileExists(url);
+
+    const exists = await fileExistsManifest(url);


Make sure to update the unit tests for setEmote

caleb-mabry · 2023-02-01T00:26:37Z

webAO/utils/binarySearch.js

+        else if (comparison < 0)
+            start = middle + 1;
+        else
+            end = middle - 1;


Can we get unit tests for this file and can you also convert it to TS?

caleb-mabry · 2023-02-01T00:26:56Z

webAO/utils/fileExists.js

+          }
+          const c_url = encodeURI(canonicalizePath(decodeURI(url.slice(AO_HOST.length))));
+
+          if(binarySearch(client.manifest, c_url) != null)


caleb-mabry · 2023-02-01T00:27:18Z

webAO/utils/paths.ts

+/* Removes `/./`, `/../`, and `//`.
+ * Does not add a leading `/` or `./`.
+ * Does not add a trailing `/`. */
+export function canonicalizePath(path: string): string {


Make sure to update the unit tests please

caleb-mabry · 2023-02-01T00:27:55Z

webAO/utils/paths.ts

+ * Does not add a leading `/` or `./`.
+ * Does not add a trailing `/`. */
+export function canonicalizePath(path: string): string {
+  const path_elements = path.split("/");


camelCasing here please

caleb-mabry · 2023-02-01T00:28:16Z

webAO/utils/tryUrls.ts

@@ -10,11 +10,11 @@ const tryUrls = async (url: string) => {
    for (let i = 0; i < urlExtensionsToTry.length; i++) {
        const extension = urlExtensionsToTry[i]
        const fullFileUrl = url + extension
-        const exists = await fileExists(fullFileUrl);
+        const exists = await fileExistsManifest(fullFileUrl);


Unit tests for this please

oldmud0 · 2023-02-01T04:07:03Z

I would suggest making separate manifests in these places:

base/characters/**/manifest.txt - basically, one manifest per character. When a character is loaded at startup, also load the manifest.
base/sound/manifest.txt
base/evidence/manifest.txt
base/background/manifest.txt
base/manifest.txt that covers the remainder.

Then make a file that instructs webAO where each manifest is located, and to preload each manifest (except for the character manifests). This would be useful for a more general mount system where there are multiple sources of assets.

There is a more esoteric approach that focuses on your particular need, which is to use filename hashes and also use their byte representation instead of text. You could also try to encode it in a tree structure like Huffman coding, e.g.

9f -- 64 -- 2d -- 1e      value: 9f642d1e
         \- 1c -- 2d      value: 9f641c2d
               \- cc      value: 9f641ccc

encoded:
9f 64 2d 1e UP UP 1c 2d UP cc
where the UP character can be anything

Salanto · 2023-02-01T06:30:12Z

Getting some air conditioning vibes rn :
https://github.com/AttorneyOnline/AO3Protocol/blob/master/assets.md

notcancername added 2 commits January 31, 2023 18:45

properly fetch, parse and use the manifest

a2c9143

use manifest

a78a7b8

Salanto requested review from caleb-mabry and stonedDiscord January 31, 2023 19:05

notcancername changed the title ~~Manifest~~ Manifest (performance improvement) Jan 31, 2023

fixup! use manifest

e1feede

notcancername force-pushed the manifest branch from 5181804 to e1feede Compare January 31, 2023 19:59

stonedDiscord previously approved these changes Jan 31, 2023

View reviewed changes

notcancername closed this Feb 1, 2023

caleb-mabry requested changes Feb 1, 2023

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Manifest (performance improvement) #182

Manifest (performance improvement) #182

notcancername commented Jan 31, 2023 •

edited

Loading

Salanto commented Jan 31, 2023 •

edited

Loading

notcancername commented Jan 31, 2023 •

edited

Loading

stonedDiscord left a comment

stonedDiscord commented Jan 31, 2023 •

edited

Loading

notcancername commented Jan 31, 2023

notcancername commented Jan 31, 2023 •

edited

Loading

notcancername commented Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

caleb-mabry Feb 1, 2023

oldmud0 commented Feb 1, 2023 •

edited

Loading

Salanto commented Feb 1, 2023

Manifest (performance improvement) #182

Manifest (performance improvement) #182

Conversation

notcancername commented Jan 31, 2023 • edited Loading

WIP

Description

Design issues

Implementation issues

Practical issues

Salanto commented Jan 31, 2023 • edited Loading

notcancername commented Jan 31, 2023 • edited Loading

stonedDiscord left a comment

Choose a reason for hiding this comment

stonedDiscord commented Jan 31, 2023 • edited Loading

notcancername commented Jan 31, 2023

notcancername commented Jan 31, 2023 • edited Loading

notcancername commented Feb 1, 2023

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

oldmud0 commented Feb 1, 2023 • edited Loading

Salanto commented Feb 1, 2023

notcancername commented Jan 31, 2023 •

edited

Loading

Salanto commented Jan 31, 2023 •

edited

Loading

notcancername commented Jan 31, 2023 •

edited

Loading

stonedDiscord commented Jan 31, 2023 •

edited

Loading

notcancername commented Jan 31, 2023 •

edited

Loading

oldmud0 commented Feb 1, 2023 •

edited

Loading