Powershell XML search performance

Question

I am working on a utility to manage shared content libraries for Work from Home scenarios. Basically I have libraries of thousands of Autodesk Revit family files, and I want to host those files on AWS S3, and then manage a local copy of the library based on what is hosted on S3. To that end I have developed an XML "index" file that lists all the folders and files in a given library, along with size, last modified date and file hash for the files. The idea being I can compare size and date in the index with size and date of file on disk and recalculate the hash only on files that need it, to ensure the "local index" represents the current state of the local library. Then I can download the "master index" and quickly compare them to determine which local files and folders to delete because they are no longer in the "master index", and more importantly which files to download because they have changed, as indicated by the different file hash. Files can change either because the user modified a local file which then need replaced with the master file again, or because the master file got revisions and the old local file needs replaced.

An index file looks like this, but a real file would have as many as 10,000 items.

<?xml version="1.0"?>
<rootDirectory>
  <item>OOTB</item>
  <item>OOTB\Data</item>
  <item>OOTB\Data\IES</item>
  <item size="583" date="03/22/2019 22:09:40" hash="B4A02121565CCADAA601C7092BD598F5BA0A9DED">OOTB\Data\IES\1x4 3Lamp.ies</item>
  <item size="582" date="06/21/2020 06:50:36" hash="CF3B1F5E8F072DE2722E940EECDE90157F3BF2EC">OOTB\Data\IES\1x4 4Lamp.ies</item>
  <item>OOTB\Data\Lookup Tables</item>
  <item>OOTB\Data\Lookup Tables\Conduit</item>
  <item size="443" date="03/22/2019 22:09:44" hash="303A0011DC5834F8072337492C4F9B305D3B0DEA">OOTB\Data\Lookup Tables\Conduit\M_Conduit Body - Type C - Aluminum.csv</item>
  <item size="380" date="03/22/2019 22:09:44" hash="60CE25A7D805BD1B3746FD21E3CF8BA9B31ACB80">OOTB\Data\Lookup Tables\Conduit\M_Conduit Body - Type C - PVC.csv</item>
  <item>OOTB\Data\Lookup Tables\Pipe</item>
  <item size="871" date="03/22/2019 22:09:44" hash="E4D246B7F9B530A82F87BFDD7680A4C150CD3015">OOTB\Data\Lookup Tables\Pipe\Elbow - Flanged - GI - Class 125.csv</item>
  <item size="731" date="03/22/2019 22:09:44" hash="DA22BD74071BFC5A4A5FB00DAABE87A5F348D647">OOTB\Data\Lookup Tables\Pipe\Elbow - Flanged - GI - Class 25.csv</item>
  <item size="879" date="03/22/2019 22:09:44" hash="2F3AE63C2A44370A48497AA2DDEC0339CAABA126">OOTB\Data\Lookup Tables\Pipe\Elbow - Flanged - GI - Class 250.csv</item>
</rootDirectory>

I have been profiling some code to update the "local index" and I have arrived at this.

$oldIndex = 'C:\Assets\Revit\oldIndex.xml'
$newIndex = 'C:\Assets\Revit\newIndex.xml'
$path = 'C:\Assets\Revit\2020'

CLS
[xml]$xml = Get-Content $oldIndex
$rootNode = $xml.SelectSingleNode('/*')
$rootPath = $rootNode.path

# Delete
(Measure-Command {
foreach ($item in $rootNode.ChildNodes) {
    $itemPath = "$rootPath\$($item.'#text')"
    if (-not (Test-Path $itemPath)) {
        $rootNode.RemoveChild($item)
    }
}
}).TotalSeconds

# Add or revise
(Measure-Command {
foreach ($filesystemItem in (Get-ChildItem $path -recurse)) {
    $itemPath = $filesystemItem.FullName.TrimStart($rootPath)
    $itemXPath = '//*[text()="' + $itemPath + '"]'
    
    if ($indexItem = $xml.SelectSingleNode('//*[text()="' + $itemPath + '"]')) {
        if ($indexItem.size -and $indexItem.date) {
            [String]$newSize = $filesystemItem.Length
            [String]$newDate = ([System.IO.FileInfo]::new($filesystemItem.FullName)).LastWriteTime
            if (($indexItem.size -ne $newSize) -or ($indexItem.date -ne $newDate)) {
                $indexItem.size = $newSize
                $indexItem.date = $newDate
                $indexItem.hash = (Get-FileHash -Path:$filesystemItem.FullName -Algorithm:SHA1).Hash
            }
        }
    } else {
        $childNode = $xml.CreateElement('item')
        $childNode.InnerText = $filesystemItem.FullName.TrimStart($path)
        if ($filesystemItem.GetType() -eq [System.IO.FileInfo]) {
            $childNode.SetAttribute('size', $filesystemItem.Length)
            $childNode.SetAttribute('date', (([System.IO.FileInfo]::new($filesystemItem.FullName))).LastWriteTime)
            $childNode.SetAttribute('hash', (Get-FileHash -Path:$filesystemItem.FullName -Algorithm:SHA1).Hash)
        }
        $rootNode.AppendChild($childNode)
    }
}
}).TotalSeconds

# Resort
(Measure-Command {
$sortedNodes = $rootNode.ChildNodes | Sort-Object {$_.InnerXml}
$rootNode.RemoveAll()

foreach ($sortedNode in $sortedNodes) {
    [void]$rootNode.AppendChild($sortedNode)
}
}).TotalSeconds

$xml.Save($newIndex)

My performance issue is in the Add or Revise section. On my test data set, of 8,000 or so files, it takes a full 17 seconds to process, even when there are only one or two changes. I have already tried using Select-Xml instead of .SelectSingleNode() as seen here.

$oldIndex = 'C:\Assets\Revit\oldIndex.xml'
[xml]$xml = Get-Content $oldIndex
$XPath = '//*[text()="OOTB\Libraries\US Imperial\Annotations\Architectural"]'

Measure-Command {
    foreach ($i in 1..1000) {
        Select-Xml -xml:$xml -xpath:$XPath
    }
}

Measure-Command {
    foreach ($i in 1..1000) {
        $xml.SelectSingleNode($XPath)
    }
}

.SelectSingleNode() out performs Select-Xml 700 ms to 2900 ms on my test data. I have also done some other tests looking at how long it takes to iterate over the files and the differences between MD5 and SHA1 for the hashing. Both where minor. I also simply remarked out the actual update lines, and I am still seeing 17 or so seconds. So it seems the root issue is in repeatedly searching the XML to determine if an item already exists and needs to be tested for revision, or doesn't exist and needs to be added. So this line

if ($indexItem = $xml.SelectSingleNode('//*[text()="' + $itemPath + '"]')) {

What I am hoping for in a review is some suggestions on optimizations in the Add or Revise section, or a verification that there really is no optimization possible.

The issue for me is the fact that I need to do this at least at every user logon, and a given machine could have multiple libraries to be indexed, perhaps even as many as 10, each with an excess of 20,000 files. If performance scales with my current numbers, I will easily be looking at close to a minute just to verify the local index of a single library, so 10 libraries is a very long process, even before I start downloading any files from S3.

Also, I should mention that I do know I could skip the sorting. For now it's really there just to facilitate me being able to review results. But given that a resort takes less than 2 seconds, compared to the 17+ for the actual required work, I may just leave the sorting in place to keep the XML "neat" in any case.

I should also mention, I considered keeping the date of the last successful index in the XML file, so I could only rehash files that had been changed since then. However, editing a file isn't the only way to get out of sync with the master library. Someone could have a copy of a much older file somewhere, and move that to the local library. Then the date isn't newer than the last successful index, but the file is still wrong and needs a new hash for comparison with the master index. So, comparing current file date and size with last indexed date and size seems like the best way to minimize hashing (which does massively impact overall time) while still ensuring that hashes are up to date.

Answer 1

This won't affect performance at all, but:

• Your date attribute uses a localized date format, but should use an ISO8601 machine-readable format instead.
• Your XML uses attributes in a sane way - thank you! I would take it even further and make item a self-closing tag, moving the text into a filename attribute.

Answer 2

Reinderien's comments definitely improve the result overall, but since my original question was about performance, I thought I should provide the answer I came up with. The main performance issue was excessive use of SelectSingleNode, when looping through all the existing files and looking to see if it was in the XML. By building two arrays, one for indexed files and one for indexed folders, I could dramatically improve the search speed. This due to .Contains() being much faster than .SelectSingleNode() and splitting folders and files into independent arrays. I have as many as 1000 folders indexed, and 8000 files, in a typical data set, and searching all 9000 items 9000 times is a lot slower than searching 1000 folders 1000 times and 8000 files 8000 times. Both of those indexes are also unsorted as there is no value in sorting them, but a slight performance penalty when creating them sorted. The last refinements where only sorting and saving the final XML if changes where actually made. With all those changes, I got total performance down to 10 seconds, when also checking all existing files to see if they have changed and need rehashed, and adding a few new files which would also need hashing. 10 seconds per library is quite manageable.

So, final code

$oldIndex = 'C:\Assets\Revit\oldIndex.xml'
$newIndex = 'C:\Assets\Revit\newIndex.xml'
$path = 'C:\Assets\Revit\2020'

function Get-FileInfo {
    param (
        [String]$path,
        [switch]$hash
    )

    $file = Get-Item $path
    $fileInfo = @{
        size = $file.Length
        date = (([System.IO.FileInfo]::new($path)).LastWriteTime).ToString('O')
        hash = $null
    }
    if ($hash) {
        $fileInfo.hash = (Get-FileHash -Path:$path -Algorithm:SHA1).Hash
    }

    $fileInfo
}

CLS
(Measure-Command {
$logAdd = [System.Collections.Generic.List[string]]::new()
$logMove = [System.Collections.Generic.List[string]]::new()
$logDelete = [System.Collections.Generic.List[string]]::new()
$logUpdate = [System.Collections.Generic.List[string]]::new()

$currentFolders = Get-ChildItem $path -Directory -recurse | Select -ExpandProperty FullName
$currentFiles = Get-ChildItem $path -File -recurse | Select -ExpandProperty FullName

[xml]$xml = Get-Content $oldIndex
$rootNode = $xml.SelectSingleNode('/*')
$rootPath = $rootNode.path

# Array to search for indexed items
$indexedFolders = [System.Collections.Generic.List[string]]::new()
$indexedFiles = [System.Collections.Generic.List[string]]::new()
foreach ($item in $rootNode.ChildNodes) {
    $indexedItems.Add($item.path)
    if ($item.hash) {
        $indexedFiles.Add($item.path)
    } else {
        $indexedFolders.Add($item.path)
    }
}


foreach ($item in $xml.SelectNodes('//item')) {
    $fullPath = "$rootPath\$($item.path)"
    $status = $null
    if (Test-Path $fullPath) {
        # Test for need to update
        if ($item.hash) { # for files only
            $fileInfo = Get-FileInfo $fullPath
            if (($item.size -ne $fileInfo.size) -or ($item.date -ne $fileInfo.date)) {
                $fileInfo = Get-FileInfo $fullPath -hash
                $item.SetAttribute('size', $fileInfo.size)
                $item.SetAttribute('date', $fileInfo.date)
                $item.SetAttribute('hash', $fileInfo.hash)
                $logUpdate.Add($fullPath.TrimStart($rootPath))
            }
        }
    } else {
        if ($item.hash) { # files
            $status = 'deleted' # assume deleted
            :current foreach ($currentFile in $currentFiles) {
                if ($currentFile.EndsWith((Split-Path $item.path -leaf))) {
                    # Only consider something moved if size and date have not changed, otherwise delete and consider it new
                    $newItemPath = $currentFile.TrimStart($rootPath)
                    $index = [array]::IndexOf($indexedFiles, $item.path)
                    $fileInfo = Get-FileInfo $currentFile
                    if (($item.size -eq $fileInfo.size) -and ($item.date -eq $fileInfo.date)) {
                        $status = 'moved'
                    }
                    Break :current
                }
            }
        } else { # folders
            $index = [array]::IndexOf($indexedFolders, $item.path)
            $status = 'deleted' # assume deleted, since a folder with the same name could exist in another sub folder and falsely indicate a move
        }

        switch ($status) {
            'deleted' {
                if ($item.hash) {
                    $indexedFiles.RemoveAt($index)
                } else {
                    $indexedFolders.RemoveAt($index)
                }
                [void]$rootNode.RemoveChild($item)
                $logDelete.Add($item.path)
            }
            'moved' {
                $item.path = $newItemPath
                if ($item.hash) {
                    $indexedFiles[$index] = $newItemPath
                } else {
                    $indexedFolders[$index] = $newItemPath
                }
                $logMove.Add($newItemPath)
            }
            default {
            }
        }
    }
}

foreach ($folder in $currentFolders) {
    $itemPath = $folder.TrimStart($rootPath)
    if (-not $indexedFolders.Contains($itemPath)) {
        $itemNode = $xml.CreateElement('item')
        $itemNode.SetAttribute('path', $itemPath)
        $rootNode.AppendChild($itemNode)
        
        $logAdd.Add($itemPath)
    }
}

foreach ($file in $currentFiles) {
    $itemPath = $file.TrimStart($rootPath)
    if (-not $indexedFiles.Contains($itemPath)) {
        $fileInfo = Get-FileInfo $file -hash
        $itemNode = $xml.CreateElement('item')
        $itemNode.SetAttribute('path', $itemPath)
        $itemNode.SetAttribute('size', $fileInfo.size)
        $itemNode.SetAttribute('date', $fileInfo.date )
        $itemNode.SetAttribute('hash', $fileInfo.hash)
        $rootNode.AppendChild($itemNode)
        $logAdd.Add($itemPath)
    }
}

if (($logDelete.Count -gt 0) -or ($logMove.Count -gt 0) -or ($logAdd.Count -gt 0) -or ($logUpdate.Count -gt 0)) {
    $sortedNodes = $rootNode.ChildNodes | Sort-Object {$_.path}
    $rootNode.RemoveAll()
    $rootNode.SetAttribute('path', $path)

    foreach ($sortedNode in $sortedNodes) {
        $rootNode.AppendChild($sortedNode)
    }

    $rootNode.SetAttribute('date', (Get-Date).ToUniversalTime().ToString('O'))

    $xml.Save($newIndex)
}

}).TotalSeconds



Write-Host "moved:$($logMove.Count) deleted:$($logDelete.Count) updated:$($logUpdate.Count) added:$($logAdd.Count)"


if ($logDelete) {
    Write-Host "Deleted:"
    foreach ($item in $logDelete) {
        Write-Host "  $item"
    }
}
if ($logMove) {
    Write-Host "Moved:"
    foreach ($item in $logMove) {
        Write-Host "  $item"
    }
}
if ($logAdd) {
    Write-Host "Added:"
    foreach ($item in $logAdd) {
        Write-Host "  $item"
    }
}
if ($logUpdate) {
    Write-Host "Updated:"
    foreach ($item in $logUpdate) {
        Write-Host "  $item"
    }
}

And the XML looks like this now.

<?xml version="1.0"?>
<rootDirectory path="C:\Assets\Revit\2020" date="2020-06-23T08:02:20.3126654Z">
  <item path="OOTB" />
  <item path="OOTB\Data" />
  <item path="OOTB\Data\IES" />
  <item path="OOTB\Data\IES\1x4 3Lamp.ies" size="583" date="2019-03-22T22:09:40.0000000+01:00" hash="B4A02121565CCADAA601C7092BD598F5BA0A9DED" />
  <item path="OOTB\Data\IES\1x41T12.ies" size="1207" date="2019-03-22T22:09:40.0000000+01:00" hash="D36BFBA468A66DD21775D0B9797479F4DBE40A19" />
  <item path="OOTB\Data\Lookup Tables" />
  <item path="OOTB\Data\Lookup Tables\Conduit" />
  <item path="OOTB\Data\Lookup Tables\Conduit\Conduit Body - Type C - Aluminum.csv" size="441" date="2019-03-22T22:09:42.0000000+01:00" hash="4E63184FEBADD10007012C94E816979B044BEF36" />
  <item path="OOTB\Data\Lookup Tables\Conduit\Conduit Body - Type C - Aluminum.csv" size="441" date="2019-03-22T22:09:42.0000000+01:00" hash="4E63184FEBADD10007012C94E816979B044BEF36" />
  <item path="OOTB\Data\Lookup Tables\Pipe" />
  <item path="OOTB\Data\Lookup Tables\Pipe\Bend Double - PVC - Sch 40 - DWV.csv" size="224" date="2019-03-22T22:09:44.0000000+01:00" hash="30C7DCD5BFC70E67CD79861CC508D72BC987F158" />
  <item path="OOTB\Data\Lookup Tables\Pipe\Bend Long Sweep - PVC - Sch 40 - DWV.csv" size="290" date="2019-03-22T22:09:44.0000000+01:00" hash="E6A8D01A99082E443744EBDE16E55612AE47611A" />
  <item path="OOTB\Libraries" />
  <item path="OOTB\Libraries\Generic" />
  <item path="OOTB\Libraries\Generic\place_holder.txt" size="0" date="2019-03-22T22:42:14.0000000+01:00" hash="DA39A3EE5E6B4B0D3255BFEF95601890AFD80709" />
  <item path="OOTB\Libraries\US Imperial" />
  <item path="OOTB\Libraries\US Imperial\Annotations" />
  <item path="OOTB\Libraries\US Imperial\Annotations\Architectural" />
  <item path="OOTB\Libraries\US Imperial\Annotations\Architectural\Casework Tag.rfa" size="274432" date="2019-03-22T22:20:42.0000000+01:00" hash="D31C94C25A2C333AAA03A122036303C6AAE0D994" />
  <item path="OOTB\Libraries\US Imperial\Annotations\Architectural\Ceiling Tag w Height.rfa" size="274432" date="2019-03-22T22:20:42.0000000+01:00" hash="8DA9958E3A746D22429175E819D620ECB78AE93E" />
  <item path="OOTB\Templates" />
  <item path="OOTB\Templates\Families" />
  <item path="OOTB\Templates\Families\English Imperial" />
  <item path="OOTB\Templates\Families\English Imperial\Annotations" />
  <item path="OOTB\Templates\Families\English Imperial\Annotations\Callout Head.rft" size="311296" date="2019-03-22T22:20:40.0000000+01:00" hash="F248371D4A9179147E6CEA0D63CF27B5D862A979" />
  <item path="OOTB\Templates\Families\English Imperial\Annotations\Data Device Tag.rft" size="307200" date="2019-03-22T22:20:22.0000000+01:00" hash="BA9421D1B4741AF773CCE716CEB81BBD4F9CA856" />
  <item path="OOTB\Templates\Families\English Imperial\Annotations\Door Tag.rft" size="307200" date="2019-03-22T22:20:40.0000000+01:00" hash="684E61A81D70BC73D0F2B62E55072D00A717A6D8" />
  <item path="OOTB\Templates\Projects" />
  <item path="OOTB\Templates\Projects\Generic" />
  <item path="OOTB\Templates\Projects\Generic\Default_I_ENU.rte" size="3248128" date="2019-03-22T22:42:14.0000000+01:00" hash="1527A4C4F7181A32F04F42233D968E4935139B90" />
  <item path="OOTB\Templates\Projects\US Imperial" />
  <item path="OOTB\Templates\Projects\US Imperial\Commercial-Default.rte" size="6410240" date="2019-03-22T22:20:30.0000000+01:00" hash="CEF8BEB4CBEF05DD9D02EAF98BC8F3E1E7657224" />
</rootDirectory>