105 lines
4.1 KiB
Java
105 lines
4.1 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Models pidgin-0001: libpurple/privacy.c
|
|
*
|
|
* add_all_buddies_to_permit_list() ensures every buddy on our buddy list is
|
|
* also on the permit (allow) list. It iterates all B buddies and for each
|
|
* calls g_slist_find_custom(account->permit, name, g_utf8_collate), scanning
|
|
* our permit GSList linearly: O(B * P) where P = permit list size (grows to B).
|
|
* Total: O(B^2) for B buddies all on our ALLOW_BUDDYLIST privacy mode.
|
|
*
|
|
* Fix: before our buddy loop, snapshot account->permit into a GHashTable for
|
|
* O(1) membership tests. Our while loop becomes O(B) total.
|
|
*/
|
|
public class PidginPrivacyTest {
|
|
|
|
// --- Defective model: GSList linear scan per buddy ---
|
|
static long addAllBuddiesDefective(List<String> buddies) {
|
|
List<String> permit = new ArrayList<>();
|
|
long ops = 0;
|
|
for (String buddy : buddies) {
|
|
// simulate g_slist_find_custom scan of permit list
|
|
boolean found = false;
|
|
for (String p : permit) { // O(P)
|
|
ops++;
|
|
if (p.equals(buddy)) { found = true; break; }
|
|
}
|
|
if (!found) permit.add(buddy);
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
// --- Fixed model: GHashTable snapshot for O(1) lookup ---
|
|
static long addAllBuddiesFixed(List<String> buddies) {
|
|
Set<String> permitSet = new HashSet<>(); // snapshot of existing permit
|
|
List<String> permit = new ArrayList<>();
|
|
long ops = 0;
|
|
for (String buddy : buddies) {
|
|
ops++; // O(1) hash lookup
|
|
if (!permitSet.contains(buddy)) {
|
|
permitSet.add(buddy);
|
|
permit.add(buddy);
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
static List<String> generateBuddies(int n) {
|
|
List<String> buddies = new ArrayList<>();
|
|
for (int i = 0; i < n; i++)
|
|
buddies.add("buddy" + i + "@example.com");
|
|
return buddies;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
System.out.println("pidgin-0001: add_all_buddies_to_permit_list O(B^2) vs O(B)");
|
|
System.out.println("============================================================");
|
|
|
|
int[] sizes = {50, 100, 200, 500, 1000, 2000};
|
|
|
|
for (int n : sizes) {
|
|
List<String> buddies = generateBuddies(n);
|
|
|
|
long tDefStart = System.nanoTime();
|
|
long opsDefective = addAllBuddiesDefective(new ArrayList<>(buddies));
|
|
long tDefEnd = System.nanoTime();
|
|
|
|
long tFixStart = System.nanoTime();
|
|
long opsFixed = addAllBuddiesFixed(new ArrayList<>(buddies));
|
|
long tFixEnd = System.nanoTime();
|
|
|
|
long timeDefective = tDefEnd - tDefStart;
|
|
long timeFixed = tFixEnd - tFixStart;
|
|
double ratio = (double) opsDefective / opsFixed;
|
|
|
|
System.out.printf("B=%4d: defective=%8d ops (%6.3f ms) | fixed=%6d ops (%6.3f ms) | ratio=%.1fx%n",
|
|
n,
|
|
opsDefective, timeDefective / 1_000_000.0,
|
|
opsFixed, timeFixed / 1_000_000.0,
|
|
ratio);
|
|
}
|
|
|
|
// Correctness: both models produce same permit list
|
|
List<String> test = Arrays.asList("alice@x.com", "bob@x.com", "alice@x.com", "carol@x.com");
|
|
|
|
Set<String> defSeen = new LinkedHashSet<>();
|
|
for (String b : test) defSeen.add(b);
|
|
|
|
Set<String> fixSeen = new HashSet<>();
|
|
List<String> fixPermit = new ArrayList<>();
|
|
for (String b : test) { if (fixSeen.add(b)) fixPermit.add(b); }
|
|
|
|
assert new ArrayList<>(defSeen).equals(fixPermit)
|
|
: "Mismatch: " + defSeen + " vs " + fixPermit;
|
|
System.out.println("\nCorrectness: PASS");
|
|
|
|
// Verify ratio at B=1000
|
|
List<String> bigBuddies = generateBuddies(1000);
|
|
long bigDef = addAllBuddiesDefective(new ArrayList<>(bigBuddies));
|
|
long bigFix = addAllBuddiesFixed(new ArrayList<>(bigBuddies));
|
|
double bigRatio = (double) bigDef / bigFix;
|
|
assert bigRatio > 200 : "Expected >200x at B=1000, got " + bigRatio;
|
|
System.out.printf("Speedup at B=1000: %.0fx -- PASS%n", bigRatio);
|
|
}
|
|
}
|