I have a feeling that something similar might be happening with WaitAll, killing performances. I'll have a look and see if I can find documentation about it.

I have a feeling that something similar might be happening with WaitAll, killing performances. I'll have a look and see if I can find documentation about it. As you are using StartNew some of the tasks might be started already so they won't be in-lined.

async static Task<IEnumerable<string>> GetAllPagesLinks(IEnumerable<string> rootUrls, bool hostMatch, bool validatePages)
{
    var result = await Task.WhenAll(rootUrls.Select(url => GetPageLinks(url, hostMatch, validatePages)));

    return result.SelectMany(x => x).Distinct();
}

static async Task<IEnumerable<string>> GetPageLinks(string formattedUrl, bool hostMatch = true, bool validatePages = true)
{
    var htmlDocument = new HtmlDocument();

    try
    {
        using (var client = new HttpClient())
            htmlDocument.Load(await client.GetStringAsync(formattedUrl));

        return htmlDocument.DocumentNode
                           .Descendants("a")
                           .Select(a => a.GetAttributeValue("href", null))
                           .Where(u => !string.IsNullOrEmpty(u))
                           .Distinct();
    }
    catch
    {
        return Enumerable.Empty<string>();
    }
}

async static Task<IEnumerable<string>> GetAllPagesLinks(IEnumerable<string> rootUrls, bool hostMatch, bool validatePages)
{
    var result = await Task.WhenAll(rootUrls.Select(url => GetPageLinks(url, hostMatch, validatePages)));

    return result.SelectMany(x => x).Distinct();
}

static async Task<IEnumerable<string>> GetPageLinks(string formattedUrl, bool hostMatch = true, bool validatePages = true)
{
    var htmlDocument = new HtmlDocument();

    try
    {
        using (var client = new HttpClient())
            htmlDocument.Load(await client.GetStringAsync(formattedUrl));

        return htmlDocument.DocumentNode
                           .Descendants("a")
                           .Select(a => a.GetAttributeValue("href", null))
                           .Where(u => !string.IsNullOrEmpty(u))
                           .Distinct();
    }
    catch
    {
        return Enumerable.Empty<string>();
    }
} 

async static Task<IEnumerable<string>> GetLinks(string url, bool hostMatch = true, bool validatePages = true, int level = 0)
{
    if (level < 0)
        throw new ArgumentOutOfRangeException(nameof(level));

    string formattedUrl = FormatAndValidateUrl(url);

    if (string.IsNullOrEmpty(formattedUrl))
        return Enumerable.Empty<string>();

    var rootUrls = await GetPageLinks(formattedUrl, hostMatch, validatePages);

    if (level == 0)
        return rootUrls;

    var links = await GetAllPagesLinks(rootUrls, hostMatch, validatePages);

    var tasks = await Task.WhenAll(links.Select(link => GetLinks(link, hostMatch, validatePages, --level)));

    return tasks.SelectMany(l => l);
}

Haven't had a chance to test it, but just get the gist.