CN102609292B

CN102609292B - 指令优化

Info

Publication number: CN102609292B
Application number: CN201110434430.0A
Authority: CN
Inventors: B·德斯梅特; H·J·M·梅杰
Original assignee: Microsoft Technology Licensing LLC
Current assignee: Microsoft Technology Licensing LLC
Priority date: 2010-12-13
Filing date: 2011-12-12
Publication date: 2016-05-04
Anticipated expiration: 2031-12-12
Also published as: WO2012082661A3; US20120151187A1; HK1173789A1; EP2652604A2; CN102609292A; WO2012082661A2; EP2652604A4

Abstract

本发明涉及指令优化。程序可在执行之前，在运行时被优化以提高性能。被指定来执行的程序指令/操作可被记录并随后在执行之前，在运行时例如通过对指令执行变换来进行优化。例如，这样的优化可移除、重新排序和/或组合指令等。

Description

指令优化

技术领域

本发明涉及指令优化。

背景技术

计算机程序是描述由计算机或其它基于处理器的设备执行的操作(即动作)的指令组。当计算机程序被加载并在计算机硬件上执行时，计算机将会跟随计算机程序的指令以预先确定的方式运转。因此，计算机变为执行可由各指令描述的任务的专用机器。

使用一种或多种编程语言的程序员创建构成计算机程序的指令。通常，源代码由程序员手动和/或在包括各种开发服务(例如，编辑器、调试器、自动填充、智能协助...)的集成开发环境(IDE)的帮助下指定或编辑。作为示例，程序员可选择利用面向对象的编程语言(例如，实现源代码，其中程序逻辑被指定为类或对象的实例之间的交互等。随后，源代码可被编译或以其他方式变换成另一形式以便于由计算机或类似设备执行。

编译器常规上从源代码为特定目标产生代码。例如，某些编译器将源代码变换成本机代码以便由特定机器执行。其它编译器从源代码生成中间代码，其中该中间代码随后在运行时被动态解释或即时(JIT)编译例如以便于在计算机平台上执行。通常，程序的大多数优化是当源代码被编译成本机或中间代码时在编译时执行的。然而，也可在代码解释或JIT编译期间在运行时执行有限的程序优化。

发明内容

下面呈现了简化的发明内容，以便提供对所公开主题的某些方面的基本概念。本发明内容不是广泛性的概观。它并不旨在标识关键/重要元素，也不旨在划定所要求保护主题的范围。其唯一目的是以简化形式呈现一些概念，作为稍后呈现的更具体实施例的序言。

简言之，本发明一般涉及指令优化。更具体地，代替在运行时急切地执行程序指令，执行也可被延后而指令可被记录。随后或并发地，所记录的指令可利用局部和/或全局优化技术来优化。例如，指令可基于其它所记录的指令来移除、重新排序和/或组合。当指令需要被执行如提供结果时，执行一组优化的指令，该组指令按照某种度量(例如，运行时间、存储器量...)不差于原始的一组指令。

为实现上述及相关目的，在此结合以下描述和附图描述了所要求保护主题的某些说明性方面。这些方面指示可实践本主题的各种方式，它们均落在所要求保护主题的范围之内。当结合附图阅读以下详细描述时，本发明的其他优点和新颖特征将变得显而易见。

附图说明

图1是指令优化系统的框图。

图2是代表性优化组件的框图。

图3是示出指令优化系统的组成的框图。

图4图形地描绘了编码为类型的查询运算符。

图5是指令优化的方法的流程图。

图6是启用运行时指令优化的方法的流程图。

图7是示出用于本公开各方面的合适操作环境的示意性框图。

具体实施方式

以下细节大体针对指令优化。指令可在执行之前，在运行时记录和变换，以改进所规定的操作的执行。这样的变换可涉及移除、重新排序和/或组合指令。换言之，可通过记录需要被执行的操作以及在执行之前优化操作而非立即执行操作来延后执行。这可被称为即时指令优化。此外，这样的功能可对应于指令虚拟化，因为对于指定的指令和被实际执行的指令包括间接层。根据一个实施例，优化可在局部、在一小组指令(例如，窥孔或窗口)上执行。另外或替换地，可采用较大型即更为全局的优化方法。

现在参考附图更详细地描述本公开的各个方面，在全部附图中用相似的标记来指示相似或相应的元素。然而应该理解，附图及其相关详细描述不旨在将所要求保护的主题限于所公开的具体形式。相反，其意图是覆盖落在所要求保护主题的精神和范围之内的所有修改、等价物和替换的方案。

首先参考图1，示出了指令优化系统100。如图所示，指令优化系统100接收、检索或以其它方式获取或获得指令或者换言之指令流(也被称为指令的流)，并输出优化指令流。这样的优化可在执行之前，在运行时执行，由内部或外部触发启动。此外，指令优化系统包括记录组件110和优化组件120。

记录组件110例如可接收、检索或其它方式获取或获得指令流，或即指定要执行的一个或多个动作的一系列指令，并在获取它们时记录这些指令。在某种意义上，创建其中指令被记录但不被执行的指令缓冲区。指令可在任何计算机可读介质上记录。

优化组件120可例如根据代数性质等(例如，域特定信息、成本...)将所记录的指令变换成优化形式。如前所述，优化可由内部或外部触发或事件触发。作为示例而非限制，优化可在记录了确定数量的指令时和/或应对于指令产生的结果的请求而触发。在一个或多个触发事件发生时，优化组件120可将所记录的指令变换成较佳的形式，以便于其指定的动作的优化执行。

将注意力转向图2，描绘了代表性优化组件120。优化组件120可包括执行优化操作的多个子组件，包括但不限于：移除组件210、重新排序组件220和组合组件230。移除组件210可移除或删除指令。例如，如果存在将元素添加到列表以及然后从该列表中移除同一元素的指令，则因为动作抵消，移除组件210可移除这两条指令。

重新排序组件220可对指令重新排序以优化计算。换言之，可能存在重新排序组件220可能试图最小化的、与指令集排列相关联的计算成本。例如，可通过在执行某一动作之前过滤数据集来改进执行，因为该数据集将有可能通过该过滤而缩减。更具体地，如果指令指示排序操作(例如，OrderBy)要在过滤操作(例如，Where)之前执行，则指令可被颠倒，使得过滤操作在排序操作之前执行，以使得就潜在缩减的数据集来执行排序操作。

组合组件230可将两个或更多个指令组合(换言之，接合)成单个指令。更具体地，可生成捕捉多个指令然后可移除其它指令的新指令。例如，代替执行要求多次遍历数据集的多个过滤操作，过滤操作可被组合，使得数据集仅需被遍历一次。

回到图1，指令优化系统100可在执行之前，在运行时操作。代替立即执行指令，执行可被延后，且指令可被记录并优化。为了清楚起见并利于理解，考虑以下类推。假定一个体(例如，人)要将三个美元金额(诸如$2.50、$0.25以及$1.50)相加在一起。该个体可简单地将金额按照所提供的方式相加在一起(例如，$2.50+$0.25＝$2.75，$2.75+$1.50＝$4.25)。然而，可通过延后计算直到获取了要相加在一起的所有值，对值重新排序然后执行计算，来使该计算较为容易。具体地，通常人们较易于将半美元(例如，$0.50)而非美元的其它分数(例如，$0.75、$0.25...)加起来。从而，代替对所看到的金额执行加法，可仅仅记录值。随后，金额可被重新排序为$2.50、$1.50和$0.25，并被计算(例如，$2.50+$1.50＝$4.00，$4.00+$0.25＝$4.25)。相同的结果以较容易计算的方式得到。指令优化系统100可对于任何机器可执行指令提供类似的功能。

经由优化组件120的优化也可在各个粒度级别执行。根据一个实施例，优化可对于一小组指令(例如，窥孔或窗口)执行。例如，优化可在对于先前的“N”个相邻指令获取了每一指令之后触发，其中“N”是正整数。另外或另选地，可采用其中在一大组指令上执行优化的更为全局的方法。例如，优化可紧接在执行之前启动，诸如当请求根据所记录的指令而产生的结果时。在一个实施例中，较简单的优化可被指定为对一小组指令执行，而更为复杂的优化可被指定为对于较大一组指令执行以利用关于指令的聚集知识。当然，这不是必需的。实际上，优化是高度可配置的，使得用户可指定要执行哪些优化以及这些优化应在何时执行。

指令优化系统100提供的功能可按照各种不同方式实现。在一个实例中，可利用动态分派，其中操作的结果展示具有用于相继操作的专门行为的对象(例如，虚拟方法)。类似地，可采用状态机，其中经由指令对附加知识的获取根据知识(换言之，状态)从一个节点移至另一个。当然，这只是所构想的两个实现机制。其它实现也是可能的，并且对于本领域技术人员而言是显而易见的。

指令优化系统100可单独使用，或与其它指令优化系统结合使用。更具体地，指令优化系统100可包括多个指令优化子系统。如图3所示，指令优化系统100可包括另外两个指令优化子系统310和320。指令优化系统100可将指令委托给子系统310和320以例如允许指令流的并行处理。此外，指令优化子系统310可将指令优化委托给另一个指令优化子系统312。换言之，指令优化系统是合成的，并相应地支持并行以及递归处理等。

作为示例而非限制，指令可涉及图形，更具体地涉及呈现多边形。馈送到指令优化系统100的指令可被划分，并被分发给指令优化子系统310和320，这些指令例如可呈现三角形。从而，呈现多边形的执行可被虚拟化，因为它被分成更简单的东西，或可呈现多个三角形来形成多边形。而且，如果确定两个多边形重叠则可进行优化，这可得到对仅一个多边形的最佳分裂(rending)。

根据一个示例性实施例，优化可对于包括查询表达式，如但不限于语言集成查询(LINQ)表达式的查询指令(即运算符)执行。用高级语言(诸如和指定的查询表达式可受益于与通过查询提供者针对的后端查询语言(例如，事务SQL)无关地工作的优化策略。

在局部级，优化可对查询运算符执行，查询运算符被表示为实现指定运算符(例如，Select、Where...)的功能的方法。而且，可利用查询运算符的语义属性以协助优化。考虑以下查询表达式：

fromxinxswherex％2＝＝0wherex％3＝＝0selectx+1

该查询表达式转成三个查询运算符方法调用(例如，Where、Where、Select)。这些运算符的朴素实现将导致创建并执行三个迭代运算。所有这些运算对源序列分开地迭代，两个执行过滤(例如，使用if语句)而另一个执行投影(例如，通过产生调用选择函数“x+1”的结果)。为了优化这一表达式，“where”过滤可被组合，而投影“select”可作为同一迭代代码的部分执行，如下：

Foreach(varxinxs)

if(x％2＝＝0&&x％3＝＝0)

yieldreturnx+1；

即使这些优化起作用，可在查询运算符级别上进行多得多的局部优化。

注意到，组合查询的能力可易于导致次优查询。具体地，可按照间接的方式编写嵌套查询表达式，很像在数据库产品中创建视图：

由于查询是可被传送的第一类对象，如上的查询可驻留在不同的地方，导致使用了不是立即明显的相邻查询运算符。例如，以上，“cheapProducts(便宜产品)”对价格建立了升序排序，而“discountTopToys(折扣热销玩具)”应用了另一种排序，实际上使得前一种排序冗余。

附录A提供了对至少查询运算符成立的一些示例性属性。对大部分而言，这些属性允许基于其的局部优化并通常允许将两个运算符折叠成一个运算符。可通过使用虚拟分派机制来实现这些和其它优化，其中序列运算符的结果展示了具有连续序列运算符应用的专门行为的对象。例如，以下示例代码示出了“OrderBy(排序按照)”调用的结果如何对直接接在该调用之后的“Where(其中)”和“OrderBy”操作起作用：

这些运算符中的每一个覆盖基类“Sequence(序列)<T>”上的虚拟方法：

序列对象保持其左侧序列对象(例如，该类型所表示的运算符所应用的对象)。子类可覆盖所提供的虚拟查询运算符方法以便进行局部优化。“Sequence<T>”实现“IEnumerable(可列举)<T>”，其实现是经由被称为“Source(源)”的抽象属性来提供的。此处，序列操作可按照LINQ查询重写。对于创建这些“Sequence<T>”对象存在不同的策略。例如，“Sequence<T>”对象可在现有的“IEnumerable<T>”扩展方法内部利用，或者可允许用户显式地移入“优化序列”世界中，例如利用“IEnumerable<T>”上的扩展方法。

图4图形地示出了运算符如何可被编码为类型以及底层“IEnumerable<T>”对象如何适应于反映正被调用的查询运算符的优化。示例示出了对“OrderBy”和“Where”子句的使用：

fromxinsourceorderbyk1orderbyk2wheref1selectx

该查询表达式被转为：

fromxinsourcewheref1orderbyk2selectx

更具体地，在查询执行时，“源”400由其优化版本封装，即“Sequence<T>”410。对于数据的操作现在可利用覆盖基类“Sequence<T>”410的虚拟方法的方法来对“Sequence<T>”410执行。当看到查询表达式“OrderBy”的第一运算符时，产生对象“OrderedSequence(有序序列)<T>”420，它捕捉关于第一键选择符(keyselector)“k1”的“OrderBy”查询运算符。当看到关于第二键选择符“k2”的第二“OrderBy”运算符时，另一“OrderedSequence<T>”对象430取消第一排序并用第二排序代替它。换言之，对两个“OrderBy”操作的查询执行计划只包括最后的“Orderby”操作，因为第一排序可作为冗余而被取消。随后，当标识“where”运算符时，“OrderedSequence<T>”440可交换过滤和排序的次序以在执行排序之前潜在地限制数据集。换言之，两个“OrderBy”操作继之以“Where”的查询计划是“Where”运算符继之以第二“OrderBy”操作。

注意到，优化可在查询构建/制定时(例如，在编译之后但在执行之前)作为调用查询运算符方法的结果而执行。该技术可用于不仅仅是“IEnumerable<T>”下的各种查询应用编程接口(API)。具体地，“Sequence<T>”层是操作的重写及其相对排序上的抽象。简单地用“源”属性类型替换支持类似运算符的另一类型将足以重写对其应用的操作。例如，该技术可用于优化“IEnumeralbe<T>”或““IObservable(可观察到)<T>”或其各自相同表现形式(homo-iconic)“IQueryable(可查询)<T>”和“IQbservable<T>”形式上的查询运算符。对于后面的形式，将向底层查询提供者提供按照高级查询操作的预先优化的查询。

为了示出重写机制的一般性质，可构建与“System.String(系统.串)”操作同构的类似的一组类型，例如为了消除冲突的操作(例如，可被抵消的那些操作)。

实际上，一般模式是具有触发优化计算的懒惰操作。在以上“String(串)”示例中，它是“ToUpper”。在“Sequence<T>”情况中，“Source”属性的列举触发优化计算。

而且，本发明的优化机制对任何不可变类型是有利的。关于不变可类型的问题是只要需要完成对应于变化或改变的某些事物，就需要创建新“事物”(例如，对象、元素...)。例如，可能存在与创建新事物、删除事物和创建新事物有关的许多指令。代替对于不可变事物执行若干分配和取消分配，所有变化可被记录，然后被用于仅创建捕捉至分配点为止所有变化的单个新不可变事物。

参考若干组件之间的交互已经描述了上述系统、架构、环境等。应该理解，这样的系统和组件可以包括这些组件或其中指定的子组件，某些指定的组件或子组件，和/或附加的组件。子组件也可以被实现为在通信上被耦合到其他组件而不是被包括在父组件中的组件。此外，一个或多个组件和/或子组件可以结合成提供聚集功能的单个组件。系统、组件、和/或子组件之间的通信可以根据推送(push)和/或拉取(pull)模型来实现。各组件也可以与一个或多个其他组件进行交互，出于简要考虑在此未具体描述该组件，但本领域的技术人员均已知。

此外，以上公开系统以及以下方法的各个部分可以包括或包含基于人工智能、机器学习或知识或规则的组件、子组件、进程、装置、方法或机制(例如，支持向量机、神经网络、专家系统、贝叶斯信任网络、模糊逻辑、数据融合引擎、分类器...)。这样的组件和其它组件可以自动化执行某些机制或进程，由此使得系统和方法的各部分更为自适应、高效及智能。作为示例而非限制，指令优化系统100可采用这样的机制来例如根据历史或上下文信息来确定或推断优化。

考虑到以上描述的示例性系统，参考图5-6的流程图将可以更好地理解依照所公开的主题实现的方法。尽管为了说明简洁起见，作为一系列框示出和描述了方法，但是，应该理解，所要求保护的主题不仅限于所描述框的顺序，一些框可以按与此处所描绘和描述的不同的顺序进行和/或与其它框并发地进行。此外，并非全部所示出的框都是实现下面所描述的方法所必需的。

参考图5，示出了便于指令优化的方法500。在参考标号510，标识、接收、检索或以其他方式获得或获取指令。在标号520，记录所标识的指令，或换言之，以不执行指令的某种方式记住指令。在参考标号530，作出是否应就指令集执行优化的判断。这样的判断可根据内部或外部触发来作出。一示例，内部触发可以是特定数量的指令的标识(例如，在标识每一指令之后优化、在标识每三个指令之后优化...)。外部触发可例如对应于对指令或更具体地由指令指定的操作产生或操纵的数据的请求。如果确定优化应被执行(“YES”)，方法500可在参考标号540继续，其中优化所记录的一组指令。然而，如果不期望优化(“NO”)，该方法可继续至参考标号510，其中标识了另一指令。可以理解，方法500可以是懒惰的。换言之，可继续收集指令，指令可形成可对优化利用的集合知识的部分，直到需要执行为止，例如以产生结果而非仅仅急切地在标识指令时执行指令。从而，方法500可被称为执行即时指令优化。

为便于清楚并理解关于所要求保护的主题的各方面起见，考虑以下真实世界比拟。假设房主指示承包商在该房主度假两周时粉刷他的房子并装上新窗户。承包商可能会在次日急切地粉刷房子并装上新窗户。或者，承包商可能仅仅注意到要粉刷房子并要装上窗户，并刚好在房主从度假回来之前，完成所有工作。换言之，承包商可虚拟化指令。然而，房主可能认为工作将在指示之后不久就开始，对房主而言，至于工作何时执行(例如，以及工作如何以及由谁执行)，没有区别。然而，在后一情况中，可优化工作执行的效率。例如，假定房主在其度假中途打电话，并改变房子的粉刷颜色。如果承包商已经粉刷了房子，他将必须用新颜色重新粉刷房子，即两倍的工作。然而，如果他还没有开始，他可仅仅改变先前记下的颜色，并在他第一次且仅有的一次粉刷房子时利用新颜色。此外，假设房主增加了诸如修屋顶的额外任务。如果承包商已经完成了工作，他有可能从工作地点撤走了其所有工具，并因此需要将它们带回来以修理屋顶。然而，如果承包商懒惰地执行工作，他可仅仅注意到向其列表增加任务。承包商然后可以等待，直到房主从度假回来之前刚好完成所有工作。当然，如果房主决定早些回家，这也可触发承包商完成列表上的所有任务。此外，可以理解，承包商不必亲自完成所有任务，而是承包商可将工作委托给一个或多个分包商，他们可执行类似的懒惰优化。

图6是启用运行时指令优化的方法600的流程图。在参考标号610，可以分析计算机程序。例如，可在编译进程期间分析源代码。在参考标号620，可基于分析对于程序注入代码以支持如本文之前所述的运行时优化。例如，利用特殊类型和虚拟分派以实现优化的代码可被注入或链接至程序。或者，指定例如基于代数性质编码优化技术的状态机的代码可被注入或链接至程序。例如，可采用修改现有指令实现的运行时库。

在此所用的术语“组件”、“系统”和“引擎”及其各种形式意指与计算机相关的实体，其可以是硬件、硬件和软件的组合、软件、或执行中的软件。例如，组件可以是但不限于是，在处理器上运行的进程、处理器、对象、实例、可执行程序、执行的线程、程序和/或计算机。作为说明，在计算机上运行的应用和计算机都可以是组件。一个或多个组件可驻留在进程和/或执行的线程内，并且组件可位于一个计算机上和/或分布在两个或更多的计算机之间。

在本文中使用的词语“示例性”或其各种形式意味着用作示例、实例或说明。在此被描述为“示例性”的任何方面或设计并不一定要被解释为相比其它方面或设计更优选或有利。此外，各示例只是出于清楚和理解的目的来提供的并且并不意味着以任何方式限制或约束所要求保护主题或本发明的相关部分。可以理解，本来可呈现不同范围的多个附加或替换示例，但出于简明的目的已被省略。

如此处所使用，术语“推论”或“推断”通常指的是从经由事件和/或数据捕捉的一组观察结果来推理或推断系统、环境、和/或用户的状态的过程。可以使用推断来标识特定上下文或动作，也可以生成例如状态上的概率分布。推断可以是概率性的，即，基于对数据和事件的考虑，计算在感兴趣状态上的概率分布。推断也可以是指用于从一组事件和/或数据构成较高级别的事件的技术。这样的推断导致从一组观察到的事件和/或存储的事件数据构建新的事件或动作，不管事件在时间上是否紧密相关，以及事件和数据是来自一个还是多个事件和数据源。可采用各种分类方案和/或系统(例如，支持向量机、神经网络、专家系统、贝叶斯信任网络、模糊逻辑、数据融合引擎……)来执行关于所要求保护主题的自动化和/或推断的动作。

而且，对于在详细描述或权利要求书中使用术语“包括”、“包含”、“具有”、“含有”或其它形式的变型而言，这样的术语旨在以类似于术语“包括”的方式体现包含性，如同“包括”在用作权利要求书中的过渡词时所解释的那样。

为了为所要求保护主题提供上下文，图7以及以下讨论旨在提供对其中可以实现本主题的各方面的合适环境的简要、概括描述。然而，合适的环境只是示例并且并非旨在对使用范围或功能提出任何限制。

尽管能够在可以在一台或多台计算机上运行的程序的计算机可执行指令的一般上下文中描述以上公开的系统和方法，但是，本领域的技术人员将认识到，各方面也可以与其他程序模块等相结合地实现。一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、组件和数据结构等。此外，本领域技术人员可以理解，上述系统和方法可用各种计算机系统配置实现，包括单处理器、多处理器或多核处理器计算机系统、小型计算设备、大型计算机、以及个人计算机、手持式计算设备(例如，个人数字助理(PDA)、电话、手表……)、基于微处理器或可编程消费者或工业电子设备等。各方面也可以在其中任务由通过通信网络链接的远程处理设备执行的分布式计算环境中实现。然而，所要求保护主题的某些方面，如果不是所有方面的话，可以在独立计算机上实施。在分布式计算环境中，程序模块可以位于本地和远程存储器存储设备中的一个或两者中。

参考图7，示出了示例通用计算机710或计算设备(例如，台式机、膝上型计算机、服务器、手持式设备、可编程消费或工业电子产品、机顶盒、游戏系统……)。计算机710包括一个或多个处理器720、存储器730、系统总线740、大容量存储750、以及一个或多个接口组件770。系统总线740与至少上述系统组件通信地耦合。然而，可以理解，在其最简单的形式中，计算机710可包括耦合到存储器730的一个或多个处理器720，该一个或多个处理器720执行存储在存储器730中的各种计算机可执行动作、指令和或组件。

处理器720可以用通用处理器、数字信号处理器(DSP)、应用程序专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑设备、分立门或晶体管逻辑、分立硬件组件或被设计为执行此处描述的功能的其任意组合来实现。通用处理器可以是微处理器，但在替换方案中，处理器可以是任何处理器、控制器、微控制器、或状态机。处理器720还可被实现为计算设备的组合，例如DSP和微处理器的组合、多个微处理器、多核处理器、结合一个DSP核的一个或多个微处理器、或任何其它这种配置。

计算机710可包括各种计算机可读介质或以其他方式与各种计算机可读介质交互以便于控制计算机710来实现所要求保护主题的一个或多个方面。计算机可读介质可以是能由计算机710访问的任何可用介质，并包含易失性和非易失性介质以及可移动和不可移动介质。作为示例而非限制，计算机可读介质可包括计算机存储介质和通信介质。

计算机存储介质包括以用于存储诸如计算机可读指令、数据结构、程序模块或其它数据这样的信息的任意方法或技术来实现的易失性和非易失性、可移动和不可移动介质。计算机存储介质包括，但不限于，存储器设备(例如，随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)……)、磁存储设备(例如，硬盘、软盘、磁带盒、磁带……)、光盘(例如，紧致盘(CD)、数字多功能盘(DVD)……)、以及固态设备(例如，固态驱动器(SSD)、闪存驱动器(例如，卡、棒、键驱动器……)……)、或者可用于存储所需信息并且可由计算机710访问的任何其他介质。

通信介质通常以诸如载波或其他传输机制等已调制数据信号来体现计算机可读指令、数据结构、程序模块或其他数据，并包括任何信息传送介质。术语“已调制数据信号”是指具有以在信号中编码信息的方式被设定或改变其一个或多个特征的信号。作为示例而非限制，通信介质包括诸如有线网络或直接线连接之类的有线介质，以及诸如声学、RF、红外及其他无线介质之类的无线介质。上面各项中的任何项的组合也应该包括在计算机可读介质的范围内。

存储器730和大容量存储750是计算机可读存储介质的示例。取决于计算设备的确切配置和类型，存储器730可以是易失性的(例如RAM)、非易失性的(例如ROM、闪存……)或是两者的某种组合。作为示例，基本输入/输出系统(BIOS)，包括诸如在启动期间在计算机710内的元件之间传输信息的基本例程，可被存储在非易失性存储器中，而易失性存储器可担当外部高速缓存存储器以便于处理器720的处理等。

大容量存储750包括相对于存储器730用于存储大量数据的可移动/不可移动、易失性/非易失性计算机存储介质。例如，大容量存储750包括但不限于，诸如磁盘或光盘驱动器、软盘驱动器、闪存存储器、固态驱动器、或记忆棒的一个或多个设备。

存储器730和大容量存储750可包括或其中存储有操作系统760、一个或多个应用762、一个或多个程序模块764和数据766。操作系统760用于控制和分配计算机710的资源。应用762包括系统和应用软件中的一个或两个，并且可利用操作系统760对资源的管理通过存储在存储器730和/或大容量存储750中的程序模块764和数据766来执行一个或多个动作。因此，应用762可根据由此提供的逻辑来将通用计算机710变成专用机器。

所要求保护主题的全部或各部分可以使用产生控制计算机以实现所公开功能的软件、固件、硬件或其任意组合的标准编程和/或工程技术来实现。作为示例而非限制，指令优化系统100或其一部分可以是应用762或形成应用762的一部分，并且包括存储在存储器和/或大容量存储750中的一个或多个模块764和数据766，这些模块和数据的功能可在由一个或多个处理器720执行时可实现。

根据一个特定实施例，处理器720可与片上系统(SOC)或在单个集成电路基座上包括或换言之集成硬件和软件的类似体系结构相对应。此处，处理器720可包括至少与处理器720和存储器730相似的一个或多个处理器以及存储器等。常规处理器包括最少量的硬件和软件并且广泛依赖于外部硬件和软件。作为对比，处理器的SOC实现更强大，因为它将硬件和软件嵌入其中以能够用最少的硬件和软件或不依赖于外部硬件和软件来启用特定功能。例如，指令优化系统100和/或相关联的功能可被嵌入到SOC体系结构中的硬件内。

计算机710还包括通信地耦合到系统总线740并方便与计算机710的交互的一个或多个接口组件770。作为示例，接口组件770可以是端口(例如，串行、并行、PCMCIA、USB、火线……)或接口卡(例如，声音、视频……)等等。在一个示例实现中，接口组件770可被具体化为用户输入/输出接口，该用户输入/输出接口使得用户能够通过一个或多个输入设备(例如，诸如鼠标等定点设备、跟踪球、指示笔、触摸垫、键盘、话筒、操纵杆、游戏手柄、圆盘式卫星天线、扫描仪、照相机、其他计算机……)来将命令和信息输入到计算机710中。在另一示例实现中，接口组件770可被具体化为输出外围接口，该输出外围接口向显示器(例如，CRT、LCD、等离子……)、扬声器、打印机和/或其它计算机等提供输出。此外，接口组件770可被具体化为网络接口，该网络接口使得能够诸如通过有线或无线通信链路与其他计算设备(未示出)通信。

以上所已经描述的内容包括所要求保护主题的各方面的示例。当然，出于描绘所要求保护主题的目的而描述每一个可以想到的组件或方法的组合是不可能的，但本领域内的普通技术人员应该认识到，所要求保护主题的许多进一步的组合和排列都是可能的。从而，所公开的主题旨在涵盖落入所附权利要求书的精神和范围内的所有这样的变更、修改和变化。

附录A

●相邻where过滤器：xs.Where(f₁).Where(f₂)＝＝xs.Where(x＝＞f₁(x)&&f₂(x))

○也用于所得到的如OfType(类型)的运算符

●相邻select投影：xs.Select(p₁).Select(p₂)＝＝xs.Select(x＝＞p₂(p₁(x))

○也用于所得到的如Cast(强制转换)的运算符

○对Zip类似，假设存在n元选择符过载

●区别的幂等：xs.Distinct().Distinct()＝＝xs.Distinct()

●冗余排序的抵消：xs.OrderBy(k₁){.ThenBy(...)}*.OrderBy(k₂)＝＝xs.OrderBy(k₂)

○对这些运算符的降序变型的使用也成立。

●排序和过滤的可交换性：xs.OrderBy(k₁).Where(f₁)＝＝xs.Where(f₁).OrderBy(k₁)

○基本原理：对经缩减的序列排序更为便宜

●N元运算符还原：

○xs.Concat(ys)＝＝EnumerableEx.Concat(xs，ys)

○EnumerableEx.Concat(xs，ys).Concat(zs)＝＝EnumerableEx.Concat(xs，ys，zs)

○也用于具有联合属性的类似运算符，诸如Union(并)

●数量的传播：

○与保持为Empty(空)的各个运算符组合的Enumerable.Empty()

○对于Return(例如，带有Select)、Throw(抛)(除非后继以Catch(接))类似注释成立。

●抵消运算符的消除：

○xs.Reverse().Reverse()＝＝xs

○这仅在输入序列不是无限的时成立。

●Skip(跳过)和Take(取)交互(当m＞＝0，n＞＝0)：

○xs.Take(m).Take(n)＝＝xs.Take(Math.Min(m，n))

○xs.Take(m).Skip(n)(wherem＞n)＝＝xs.Skip(n).Take(m-n)

○xs.Skip(m).Skip(n)＝＝xs.Skip(m+n)

●中间分配的缩减：

○xs.ToArray().ToArray()＝＝xs.ToArray()

○xs.ToList().ToList()＝＝xs.ToList()

○一般而言，之后的.To*运算符消除之前这样的.To*运算符的需要

●将中间分配向下推送：

○xs.To[Array|List]().[Where|Select|...]＝＝

xs.[Where|Select|...].To[Array|List]()

○这仅在输入序列不是无限的时成立。

●Reverse(颠倒)和OrderBy改变排序方向：

○xs.OrderBy(k₁).Reverse()＝＝xs.OrderByDescending(k₁)

○xs.OrderByDescending(k₁).Reverse()＝＝xs.OrderBy(k₁)

Claims

1.一种优化指令的方法，包括：

采用被配置来执行存储在存储器(730)中的计算机可执行指令的至少一个处理器(720)以执行以下动作：

记录被指定来执行的指令的流，所述指令包括语言集成查询表达式；以及

在执行所记录的查询指令之前，先在运行时优化所记录的查询指令，所述优化与目标数据源查询语言无关，其中所述优化在记录了确定数量的指令时触发和/或应以下请求而触发：即对所记录的指令产生的结果的请求。

2.如权利要求1所述的方法，其特征在于，在向所记录的查询指令添加指令时增量式地优化所记录的查询指令。

3.如权利要求2所述的方法，其特征在于，全局地优化所记录的查询指令。

4.如权利要求1所述的方法，其特征在于，全局地优化所记录的查询指令。

5.如权利要求1所述的方法，其特征在于，还包括延后优化所记录的查询指令直到所述指令的执行产生的结果被请求。

6.一种指令优化系统(100)，包括：

耦合到存储器(730)的处理器(720)，所述处理器(720)被配置来执行存储在所述存储器(730)中的以下计算机可执行组件：

被配置成记录指定来执行的查询指令的第一组件(110)，所述查询指令包括语言集成查询表达式；以及

被配置成与优化所记录的指令的第二组件(120)，所述优化与目标数据存储查询语言无关，其中所述第一和第二组件在执行所记录的指令之前，在运行时操作，其中所述优化在记录了确定数量的指令时触发和/或应以下请求而触发：即对所记录的指令产生的结果的请求。

7.如权利要求6所述的系统，其特征在于，所述第二组件被配置成在记录指令时增量式地优化所记录的指令。

8.如权利要求7所述的系统，其特征在于，所述第二组件被配置成全局地优化所记录的指令。

9.如权利要求6所述的系统，其特征在于，所述第二组件被配置成当所记录的指令中的一条或多条将要被执行时全局地优化所记录的指令。

10.如权利要求6所述的系统，其特征在于，所述第二组件被配置成延后所记录的指令的优化，直到所述指令的执行产生的结果被请求。