Skip to content

perf: NewKey() and NewSection() use O(n) linear scan for existence check #377

@Liudon

Description

@Liudon

Version

1.67.1

Describe the bug

Section.NewKey() and File.NewSection() both use inSlice() to check
whether a key or section already exists. inSlice() performs a linear scan over
a []string slice, resulting in O(n) time complexity per call.

https://github.com/go-ini/ini/blob/main/section.go#L78
https://github.com/go-ini/ini/blob/main/file.go#L97

To reproduce

Create a section with a large number of keys, then call NewKey() with an
existing key name. The cost grows linearly with the number of keys:

f := ini.Empty()
sec, _ := f.NewSection("test")

// Pre-populate 1000 keys
for i := 0; i < 1000; i++ {
    sec.NewKey(fmt.Sprintf("key%d", i), "val")
}

// This call scans all 1000 keys via inSlice() — O(n)
sec.NewKey("key999", "newval")

The same pattern applies to File.NewSection() with a large number of
sections.

Expected behavior

Key and section existence checks should use the already available map for
O(1) constant-time lookup, instead of scanning the entire slice. The cost of
NewKey() and NewSection() should not grow with the number of existing
entries.

Additional context

No response

Code of Conduct

  • I agree to follow this project's Code of Conduct

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions