UNDF: UNDF-2026-000000481

octave-0002: load_path::add — O(D²) directory-presence scan on path initialization

Summary

Field	Value
ID	octave-0002
Severity	MEDIUM
CWE	CWE-407 (Algorithmic Complexity)
File	`libinterp/corefcn/load-path.cc`
Functions	`load_path::find_dir_info`, `load_path::add`
Lines	1021–1055, 1105–1155
Speedup	~500x op-count at D=1000 dirs

Defect

Every call to load_path::add(dir, ...) calls find_dir_info(dir) (lines 1119, 1151), which is an O(D) linear scan over the m_dir_info_list:

// load-path.cc:1029
while (retval != m_dir_info_list.cend ())
  {
    if (retval->m_dir_name == dir)   // O(D) string compare per call
      break;
    retval++;
  }

load_path::set() (called at startup from initialize()) loops over all N path elements and calls append() → add() for each one:

// load-path.cc:346
for (const auto& elt : elts)
  append (elt, warn);   // each append → add → find_dir_info (O(D))

Since m_dir_info_list grows by 1 per iteration, the total cost is: 1 + 2 + ... + N = O(N²).

Additionally, each add() call issues a second find_dir_info(".") call at line 1151 to keep "." at the front — doubling the quadratic work.

A standard Octave installation ships with ~200+ path directories via OCTAVE_PATH and restoredefaultpath. Toolbox-heavy environments (Octave Forge, biomedical packages) can exceed 500+ directories.

Root Cause

m_dir_info_list is a std::list<dir_info> with no parallel index. Membership is checked by linear scan every time a directory is added. This is O(N²) overall for N-directory path initialization.

Fix

Maintain a std::unordered_set<std::string> m_dir_name_set in load_path alongside m_dir_info_list. Replace the find_dir_info loop with O(1) set membership, and maintain the set in sync with the list on add/remove.

--- a/libinterp/corefcn/load-path.h
+++ b/libinterp/corefcn/load-path.h
@@ -... @@
+  std::unordered_set<std::string> m_dir_name_set;

--- a/libinterp/corefcn/load-path.cc
+++ b/libinterp/corefcn/load-path.cc
@@ -1021,10 +1021,12 @@
 load_path::find_dir_info (const std::string& dir_arg) const
 {
   std::string dir = ...;
-  auto retval = m_dir_info_list.cbegin ();
-  while (retval != m_dir_info_list.cend ())
-    {
-      if (retval->m_dir_name == dir)
-        break;
-      retval++;
-    }
-  return retval;
+  // O(1) fast path: check set membership before walking the list
+  if (m_dir_name_set.find (dir) == m_dir_name_set.end ())
+    return m_dir_info_list.cend ();
+  // Only walk list to get iterator when dir is actually present (rare)
+  auto retval = m_dir_info_list.cbegin ();
+  while (retval != m_dir_info_list.cend ())
+    {
+      if (retval->m_dir_name == dir) break;
+      retval++;
+    }
+  return retval;
 }
@@ -1119 +1121 @@
+  m_dir_name_set.insert (di.m_dir_name);
   if (at_end)
     m_dir_info_list.push_back (di);
@@ -remove @@
+  m_dir_name_set.erase (di.m_dir_name);
   m_dir_info_list.erase (...);

The fix eliminates the O(D) scan for the common case (dir not yet present). Total path initialization cost drops from O(D²) to O(D).

Measurement

Simulated with OctaveLoadPathAlgorithm.java:

D	slow ops	fast ops	ratio
100	10,200	200	51×
500	251,000	1,000	251×
1000	1,002,000	2,000	501×

References

libinterp/corefcn/load-path.cc lines 1021–1055 (find_dir_info)
libinterp/corefcn/load-path.cc lines 1105–1155 (add)
libinterp/corefcn/load-path.cc lines 346–347 (set loop)

3.7 KiB Raw Permalink Blame History Unescape Escape